poj 2115 C Looooops(模线性方程)

2019-04-13 20:41发布

站内文章 / 模拟电子
10188 0 1039
http://poj.org/problem?id=2115
题意：对于C的循环（for i = A; i != B; i+=C）问在k位存储系统内循环多少次结束； 　　　若循环有限次能结束输出次数，否则输出 FOREVER； 解：设x为循环次数； 　  (A+C*x)%2^k = B;　　 　　则 C*x+A = 2^k*y+B;  　　所以 C*x - 2^k*y = B-A; 类似于a*x+b*y = c （或 a*x = c(mod b))模线性方程的形式，根据扩展欧几里得算法解决，模板题。
#include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-8 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 10; /* (A+C*x)%2^k = B; 那么 A + C*x = 2^k * y + B; C*x - 2^k*y = B-A; */ LL extend_gcd(LL a, LL b, LL &x, LL &y) { if(b == 0) { x = 1; y = 0; return a; } LL d = extend_gcd(b,a%b,x,y); LL t = x; x = y; y = t - a/b*y; return d; } int main() { int A,B,C,k; LL a,b,c; LL x,y; while(~scanf("%d %d %d %d",&A,&B,&C,&k)) { if(A == 0 && B == 0 && C == 0 && k == 0) break; a = C; b = 1LL<


热门文章