2018 Wannafly summer camp Day2--Utawarerumono
12744 ワード
Utawarerumono記述テーマ記述:算数は数少ないが長い間厄介になることである.いつも彼女はハックに手伝ってもらうが、ハックはもう買い物に派遣された.そこで彼女はあなたに助けを求めた.
変数x,yに関する不定方程式a x+b y=cax+by=cax+by=cを与え,この方程式には複数の整数解がある可能性があることは明らかである.もし解があれば、p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗y p_2∗x^2+p_1∗x+q_2∗y^2+q_1∗y p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗yの最小の整数解のセットは何ですか.便宜上、p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗y p_を出力するだけです.2∗x^2+p_1∗x+q_2∗y^2+q_1∗y p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗yの最小値.
入力:1行目の3つのスペースで区切られた整数a,b,c(0≦a,b,c≦1 0 5)a,b,c(0≦a,b,c≦10^5)a,b,c(0≦a,b,c≦105)
2行目の2つのスペースで区切られた整数p 1,p 2(1≦p 1,p 2≦1 0 5)p_1,p_2(1≤p_1,p_2≤10^5) p1,p2(1≤p1,p2≤105).
3行目の2つのスペースで区切られた整数q 1,q 2(1≦q 1,q 2≦1 0 5)q_1,q_2(1≤q_1,q_2≤10^5) q1,q2(1≤q1,q2≤105).
出力:方程式に整数解がない場合、``Kuon’’を出力します.
整数解があれば、p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗y p 2∗x^2+p 1∗x+q 2∗y^2+q 1∗y p 2∗x+p 1∗x+q 2∗yの最小値を出力する.
サンプル入力2 2 1 1サンプル出力Kuonは、一次項の影響が小さいため、二次項p 2∗x 2+q 1∗y 2=p 2∗((c−b y)/a)2+q 2∗y 2 p_2*x^2+q_1*y^2=p_2*((c-by)/a)^2+q_2*y^2 p 2∗x 2+q 1∗y 2=p 2∗((c−by)/a)2+q 2∗y 2,O(a)O(a)O(a)O(a)の∣y|y|∣y∣y∣の取値がc−b y c−by c−by c−by c−by c−by c−byはa a aの倍数であり,このとき∣(c−b y)/a∣|(c−by)/a|a|a|a|a|a|a|b|a|a|b|a|a|byはa a a aの倍数であり,このとき∣(c−b(c−b−∣(c−by)/a∣はO(c+b)O(c+b)O(c+b)O(c+b)であり、これにより1 0 18 10^{18}1018を超えない解のセットが得られる.答えはもっと大きくありません多項式の値はXの絶対値が増加するとx<0 x<0 x<0 x<0のときのみ小さくなり,x<(−p 1)/2 p 2 x<(-p_1)/2 p_2 x<(−p 1)/2 p 2の値は依然として大きくなるので、x x xまたはy y yの値を暴力的に列挙することができる(1 e 5 1 e 5 1 e 5で済む).
変数x,yに関する不定方程式a x+b y=cax+by=cax+by=cを与え,この方程式には複数の整数解がある可能性があることは明らかである.もし解があれば、p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗y p_2∗x^2+p_1∗x+q_2∗y^2+q_1∗y p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗yの最小の整数解のセットは何ですか.便宜上、p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗y p_を出力するだけです.2∗x^2+p_1∗x+q_2∗y^2+q_1∗y p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗yの最小値.
入力:1行目の3つのスペースで区切られた整数a,b,c(0≦a,b,c≦1 0 5)a,b,c(0≦a,b,c≦10^5)a,b,c(0≦a,b,c≦105)
2行目の2つのスペースで区切られた整数p 1,p 2(1≦p 1,p 2≦1 0 5)p_1,p_2(1≤p_1,p_2≤10^5) p1,p2(1≤p1,p2≤105).
3行目の2つのスペースで区切られた整数q 1,q 2(1≦q 1,q 2≦1 0 5)q_1,q_2(1≤q_1,q_2≤10^5) q1,q2(1≤q1,q2≤105).
出力:方程式に整数解がない場合、``Kuon’’を出力します.
整数解があれば、p 2∗x 2+p 1∗x+q 2∗y 2+q 1∗y p 2∗x^2+p 1∗x+q 2∗y^2+q 1∗y p 2∗x+p 1∗x+q 2∗yの最小値を出力する.
サンプル入力2 2 1 1サンプル出力Kuonは、一次項の影響が小さいため、二次項p 2∗x 2+q 1∗y 2=p 2∗((c−b y)/a)2+q 2∗y 2 p_2*x^2+q_1*y^2=p_2*((c-by)/a)^2+q_2*y^2 p 2∗x 2+q 1∗y 2=p 2∗((c−by)/a)2+q 2∗y 2,O(a)O(a)O(a)O(a)の∣y|y|∣y∣y∣の取値がc−b y c−by c−by c−by c−by c−by c−byはa a aの倍数であり,このとき∣(c−b y)/a∣|(c−by)/a|a|a|a|a|a|a|b|a|a|b|a|a|byはa a a aの倍数であり,このとき∣(c−b(c−b−∣(c−by)/a∣はO(c+b)O(c+b)O(c+b)O(c+b)であり、これにより1 0 18 10^{18}1018を超えない解のセットが得られる.答えはもっと大きくありません多項式の値はXの絶対値が増加するとx<0 x<0 x<0 x<0のときのみ小さくなり,x<(−p 1)/2 p 2 x<(-p_1)/2 p_2 x<(−p 1)/2 p 2の値は依然として大きくなるので、x x xまたはy y yの値を暴力的に列挙することができる(1 e 5 1 e 5 1 e 5で済む).
#include
");
if(((a==0)&&(b==0)&&c) || c%d!=0 )
printf("Kuon
");
else if(a&&b==0){
if(c%a!=0){
printf("Kuon
");
}else{
ll ta=c/a;
ll ee=p2*ta*ta+p1*ta;
cout<<ee<<endl;
}
}
else if(a==0&&b)
{
if(c%b!=0)
printf("Kuon
");
else{
ll tc=c/b;
ll eee=q2*tc*tc+q1*tc;
cout<<eee<<endl;
}
}
else{
for(int i=-100005;i<=100005;i++){
if((c-a*i)%b==0){
ll iy=(c-a*i)/b;
ll ac=p2*i*i+p1*i+q2*iy*iy+q1*iy;
ans=min(ans,ac);
}
}
cout<<ans<<endl;
}
return 0;
}