模线性方程----zoj_2305

2019-04-13 14:26发布

站内文章 / 模拟电子
11132 0 1717
    推论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 。
    以上定理的具体证明见《算法导论》。     实用模板     扩展欧几里德算法 int Extended_Euclid(int a,int b,int& x,int &y) { if(b==0){ x=1; y=0; return a; } int d=Extended_Euclid(b,a%b,x,y); int temp=x;x=y;y=temp-a/b*y; return d; }  用扩展欧几里得解模线性方程ax=b (mod n)   bool modularLinearEquation(int a,int b,int n) { int x,y,x0,i; int d=Extended_Euclid(a,n,x,y); if(b%d) return false; x0=x*(b/d)%n; for(i=1;i<=d;i++) printf("%d ",(x0+i*(n/d))%n); return true; } zoj_2305(这里是求最小解) #include 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 "); else printf("%lld ",jud); } return 0; }   

热门文章