解方程（来自学长的“遗产”）

解方程

题目描述

解出一元二次方程ax+by=c的一组解(x0, y0),使|x0+y0|最小。

输入格式

共一行，三个整数a,b,c。

输出格式

共一行，为|x0+y0|的最小值。

若无解输出“kito”。

样例

样例输入1

1 1 1

样例输出1

样例输入2

2 3 1

样例输出2

数据范围与提示

有30%的数据 a,b均为质数,c=1。

另有20%的数据 a,b,c均为质数。

100%的数据 a,b,c<=1,000,000,000。

思路：这就是一道数学题（扩欧）。运用扩欧求出一组解，这样解的通式为：x0-b/gcd(a,b)*t,y0+a/gcd(a,b)*t(或者x0+b/gcd(a,b)*t,y0-a/gcd(a,b)*t),这里写a/gcd(a,b),而不是a是因为若数过大容易漏掉一些答案，此时可以暴力枚举t的值（注意负值也要枚举），不过会T，可以多想一下，要求|x+y|,|x+y|=|x0+y0+(a-b)/gcd(a,b)*t|，此时x0+y0已知(a-b)/gcd(a,b)已知，将其看成|b+k*t|,最小值即为0时，t=-b/k,若t不为整数，答案可以为|b|，|b|%t,|b|%t-t(因为两边可能不对称)

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int inf=0x3f3f3f3f;
 5 typedef long long ll;
 6 ll x,y;
 7 ll gcd(int a,int b){
 8     if(b==0) return a;
 9     return gcd(b,a%b);
10 }
11 void expand(int a,int b){
12     if(b==0){
13         x=1;
14         y=0;
15         return;
16     }
17     expand(b,a%b);
18     ll t=x;
19     x=y;
20     y=t-a/b*y;
21 }
22 int main(){
23     int a,b,c;
24     scanf("%d%d%d",&a,&b,&c);
25     if(c%(gcd(a,b))!=0){
26         printf("kito
");
27         return 0;
28     }    
29     ll k=c/(gcd(a,b));
30     expand(a,b);
31     ll xx=x*k;
32     ll yy=y*k;
33     ll aa=a/(gcd(a,b));
34     ll bb=b/(gcd(a,b));
35     ll d=abs(xx+yy);
36     ll ans=d;
37     ll dd=abs(aa-bb);
38     if(dd!=0) ans=min(ans,min(d%dd,abs(d%dd-dd)));
39     printf("%lld
",ans);
40     return 0;
41 }

View Code