| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 18926 | Accepted: 4973 |
Description
for (variable = A; variable != B; variable += C)
statement;
Input
Output
Sample Input
3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 0
Sample Output
0 2 32766 FOREVER
题意：for(x=A;x!=B;x+=C,x%=1LL<<k) 求解结束时循环的次数
思路：显然是求解方程(A+Cx)%n=B，(n=1<<k)，变形得Cx%n=(B-A)%n，即转为模线性同余方程 Cx=(B-A)(mod n)，扩展gcd解之即可
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000100; const int INF=(1<<28); typedef long long ll; ll A,B,C,k; ll x,y; ll exgcd(ll a,ll b, ll &x, ll &y) { if(b==0){ x=1;y=0; return a; } ll r=exgcd(b,a%b,x,y); ll t=y; y=x-a/b*y; x=t; return r; } bool mod_linear_equation(ll a,ll b,ll n) { ll d=exgcd(a,n,x,y); if(b%d) return false; x=x*(b/d)%n; x=(x%(n/d)+n/d)%(n/d); return true; } int main() { while(cin>>A>>B>>C>>k,A||B||C||k){ if(mod_linear_equation(C,B-A,1LL<<k)) cout<<x<<endl; else cout<<"FOREVER"<<endl; } return 0; }
poj2115——拓展欧几里德求模线性同余方程的最小正整数解
原文：http://www.cnblogs.com/--560/p/4372794.html
