点击刷新
http://poj.org/problem?id=1061
第一遍的写法：
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; long long x,y,m,n,l,j1,j2; long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); } void extend(long long a,long long b,long long &x1,long long &y1) { if(b==0) { x1=1; y1=0; return ; } extend(b,a%b,x1,y1); long long t=x1; x1=y1; y1=t-a/b*y1; return ; } int main() { while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF) { long long a=n-m; long long b=l; long long c=x-y; long long temp=gcd(a,b); if(c%temp!=0||n==m) { printf("Impossible\n"); continue; } a/=temp; b/=temp; c/=temp; extend(a,b,j1,j2); long long t=-(j1*c)/b; j1=c*j1+t*b; if(j1<0) { if(b>0) j1+=b; } printf("%lld\n",j1); } return 0; }
第二遍：
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; long long x,y,m,n,l,j1,j2; long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); } void extend(long long a,long long b,long long &x1,long long &y1) { if(b==0) { x1=1; y1=0; return ; } extend(b,a%b,x1,y1); long long t=x1; x1=y1; y1=t-a/b*y1; return ; } int main() { while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF) { long long a=n-m; long long b=l; long long c=x-y; long long temp=gcd(a,b); if(c%temp!=0||n==m) { printf("Impossible\n"); continue; } a/=temp; b/=temp; c/=temp; extend(a,b,j1,j2); long long t=((j1*c)%b+b)%b; printf("%lld\n",t); } return 0; }
POJ2115:
题意：
对于C的for(i=A ; i!=B ;i +=C)循环语句，问在k位存储系统中循环几次才会结束。
若在有限次内结束，则输出循环次数。
否则输出死循环。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; long long a,b,c,k; long long x1,x2; long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); } void extend(long long A,long long B,long long &x1,long long &y1) { if(B==0) { x1=1; y1=0; return ; } extend(B,A%B,x1,y1); long long t=x1; x1=y1; y1=t-(A/B)*y1; } int main() { while(scanf("%lld%lld%lld%lld",&a,&b,&c,&k)!=EOF) { if(a==0&&b==0&&c==0&&k==0) break; long long A=c; long long B=pow(2,k); long long C=b-a; long long temp=gcd(A,B); if(C%temp) { printf("FOREVER\n"); continue; } A/=temp; B/=temp; C/=temp; extend(A,B,x1,x2); long long t=(C*x1%B+B)%B; printf("%lld\n",t); } return 0; }
题目解析：
这两道题目都是简单的扩展欧几里得求二元一次方程最优解，理解了就好做了，浪费了一天多的时间才搞透，脑残的孩子果断得慢慢学。
更通常的是：我们需要求解方程的最小整数解 若我们已经求得x0,y0为方程中x的一组特解，那么 x=x0+b/gcd(a,b)*t，y=y0-a/gcd(a,b)*t(t为任意整数）也为方程的解 且b/gcd(a,b)，a/gcd(a,b)分别为x，y的解的最小间距，所以x在0~b/gcd(a,b)区间有且仅有一个解， 同理y在0~a/gcd(a,b)同样有且仅有一个解，这个解即为我们所需求的最小正整数解。
为什么b/gcd(a,b)，a/gcd(a,b)分别为x，y的解的最小间距？ 解：假设c为x的解的最小间距，此时d为y的解的间距，所以x=x0+c*t，y=y0-d*t（x0，y0为一组特解，t为任意整数） 带入方程得：a*x0+a*c*t+b*y0-b*d*t=n,因为a*x0+b*y0=n，所以a*c*t-b*d*t=0，t不等于0时，a*c=b*d 因为a,b,c,d都为正整数，所以用最小的c，d，使得等式成立，ac，bd就应该等于a，b的最小公倍数a*b/gcd(a,b), 所以c=b/gcd(a,b)，d就等于a/gcd(a,b)。
所以，若最后所求解要求x为最小整数，那么x=(x0%（b/gcd(a,b))+b/gcd(a,b))%(b/gcd(a,b))即为x的最小整数解。 x0%（b/gcd(a,b))使解落到区间-b/gcd(a,b)~b/gcd(a,b)，再加上b/gcd(a,b)使解在区间0~2*b/gcd(a,b)， 再模上b/gcd(a,b)，则得到最小整数解（注意b/gcd(a,b)为解的最小距离，重要）
UVA10673Play with Floor and Ceil
题目解析：
超级大水题，模版题。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; long long p,q,x,k; long long x1,x2; long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); } void extend(long long a,long long b,long long &x1,long long &y1) { if(b==0) { x1=1; y1=0; return ; } extend(b,a%b,x1,y1); long long t=x1; x1=y1; y1=t-a/b*y1; return ; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%lld%lld",&x,&k); long long a=floor((double)x/(double)k); long long b=ceil((double)x/(double)k); long long c=x; long long temp=gcd(a,b); a/=temp; b/=temp; c/=temp; extend(a,b,x1,x2); x1=x1*c; x2*=c; printf("%lld %lld\n",x1,x2); } return 0; }
© 著作权归作者所有
发表评论
