首页 > 代码库 > cogs2057 殉国 扩展欧几里得
cogs2057 殉国 扩展欧几里得
填坑……链接：http://cogs.pro/cogs/problem/problem.php?pid=2057
题意：求出方程$ax+by=c$的两组解使得$x+y$分别最小，最大，并求出共有多少组非负整数解。
首先，他给出了$a$、$b$，我们就可以搞出来一组解$x0$、$y0$。如果这组解非法或者压根没解，那就是没有正整数解。否则，我们就利用$x=x0+kb$，$y=y0+ka$分别求解。
显然，根据$a$、$b$的大小，我们可以判断$k$最小或最大时解总和最大或最小，直接输出时判断即可。至于解的数量，则直接用$(xmax-xmin)/a+1$计算即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 long long exgcd(long long a,long long b,long long &x,long long &y) 7 { 8 if(!b) 9 { 10 x=1,y=4; 11 return a; 12 } 13 int d=exgcd(b,a%b,x,y); 14 long long tmp=x;x=y;y=tmp-y*(a/b); 15 return d; 16 } 17 int haha() 18 { 19 freopen("BlackHawk.in","r",stdin); 20 freopen("BlackHawk.out","w",stdout); 21 long long a,b,c;scanf("%lld%lld%lld",&a,&b,&c); 22 long long x,y,x2,y2,ans1,ans2; 23 long long g=exgcd(a,b,x,y); 24 if(c%g) 25 { 26 printf("-1 -1\n0\n"); 27 return 0; 28 } 29 a/=g,b/=g,c/=g; 30 x*=c;y*=c; 31 y%=a;y=(y+a)%a;x=(c-b*y)/a; 32 if(x<0||y<0) 33 { 34 printf("-1 -1\n0\n"); 35 return 0; 36 } 37 ans1=x+y; 38 x2=x%b;y2=(c-a*x2)/b;ans2=x2+y2; 39 printf("%lld %lld\n%lld",min(ans1,ans2),max(ans1,ans2),abs(x2-x)/b+1); 40 } 41 int sb=haha(); 42 int main(){;}
cogs2057 殉国 扩展欧几里得
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。