模线性方程----zoj_2305
??? 推论1：方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a,n) | b。
??? 推论2：方程ax=b(mod n)或者对模n有d个不同的解，其中d=gcd(a,n)，或者无解。
??? 定理1：设d=gcd(a,n)，假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b，则方程ax=b(modn)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e?mod(n/d)，最大整数解x2=x1+(d-1)*(n/d)。
??? 定理2：假设方程ax=b(mod n)有解，且x0是方程的任意一个解，则该方程对模n恰有d个不同的解(d=gcd(a,n))，分别为：xi=x0+i*(n/d) mod n 。
??? 以上定理的具体证明见《算法导论》。
??? 实用模板
??? 扩展欧几里德算法
#include <cstdio> long long exgcd(long long a, long long b, long long &x,long long &y){ if (b == 0) { x = 1, y = 0; return a; } long long re = exgcd(b, a % b, x ,y); long long tmp = x; x = y; y = tmp - a / b * y; return re;}long long modular_linear(long long a,long long b,long long n){ long long x,y; long long d = exgcd(a,n,x,y); if (b % d) { return -1; } long long re = x*(b/d) %n + n; re = re%(n /d); return re;}int main(){ long long A,B,C,K; while (scanf("%lld %lld %lld %lld",&A,&B,&C,&K)== 4 &&(A||B||C||K)) { long long jud = modular_linear(C,B-A,1LL << K); if (jud == -1) printf("FOREVER\n"); else printf("%lld\n",jud); } return 0;} ??