POJ 2115 （模线性方程 -> 扩展欧几里得）

2019-04-14 16:28发布

站内文章 / 模拟电子
13384 0 1193

题意： for(i=A ; i!=B ;i +=C)循环语句，问在k位操作系统中循环结束次数。 若在有则输出循环次数。 否则输出死循环。
存在这样的情况；i= 65533 ；i<=2；i+= 4；时i = 2； 由模线性方程->扩展欧几里得、
如何求x的最小正解 x = （x%b+b）%b y = （y%a+a）%a #include #include #include #include #include using namespace std; #define MIN INT_MIN #define MAX INT_MAX #define N 204 #define LL __int64 LL int gcd(LL n,LL m) { LL r; while(m!=0) { r = n%m; n = m; m = r; } return n; } void exgcd(LL a,LL b,LL &x1,LL &y1) { if(b==0) { x1=1; y1=0; return ; } exgcd(b,a%b,x1,y1);//辗转相除 LL t=x1; x1=y1; y1=t-a/b*y1; //设n%b = a;-> a = n - n/b; return ; } int main() { LL a,b,c,k; while(~scanf("%I64d %I64d %I64d %I64d",&a,&b,&c,&k)) { // int sum = 0; if(a==0&&b==0&&c==0&&k==0) break; /* for(int i = 1;i<=7;i+=2) { sum++; cout< 直接ex_gcd #include #include #include #include #include #include #define MIN INT_MIN #define MAX INT_MAX const int N = 210; typedef long long LL; using namespace std; LL ex_gcd(LL a,LL b,LL &x1,LL &y1) { if(b==0) { x1 = 1; y1 = 0; return a; } LL d = ex_gcd(b,a%b,x1,y1); LL t = x1; x1 = y1; y1 = t - a/b*y1; return d; } int main() { LL a,b,c,k; while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&k)) { if(a==0&&b==0&&c==0&&k==0) break; LL A = c; LL B = (LL)1<

热门文章