解线性同余方程的应用(一)

 例题一 

题目如图所示

典型的解同余方程组的题目，代码如下

#include<cstdio> #include<iostream> #include<cstring> using namespace std; 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 ans=exgcd(b,a%b,x,y); long long temp=x; x=y; y=temp-a/b*y; return ans; } int main() { long long i,n,a1,r1,a2,r2,a,b,c,x0,y0; while(scanf("%lld",&n)!=EOF) { bool ifhave=1; scanf("%lld%lld",&a1,&r1); for(i=1;i<n;i++) { scanf("%lld%lld",&a2,&r2); a=a1,b=a2,c=r2-r1; long long g=exgcd(a,b,x0,y0); if(c%g!=0) { ifhave=0; } int t=b/g; x0=(x0*(c/g)%t+t)%t; r1=a1*x0+r1; a1=a1*a2/g; } if(ifhave==0) { printf("-1\n"); continue; } printf("%lld\n",r1); } return 0; }

例题2

c looooops(pku 2115)

对于循环语句

for(variable=A; variable!=B;variable+=C )

statement;

已知所有的数均为k进制无符号整数类型，给出A,B,C和k的值，计算并输出statement执行的次数， 如果执行的次数为无限次，那么直接输出"FOREVER"。

输入：输入数据有多组，每组数据占一行，有四个整数A,B,C,k（0<=A,B,C<2^k）,输入为0 0 0 0时程序结束。

输出：对于每组数据，输出执行的次数，如果为无限次，那么直接输出"FOREVER";

分析：

题意不难理解，只是利用了 k位存储系统 的数据特性进行循环。

例如int型是16位的，那么int能保存2^16个数据，即最大数为65535（本题默认为无符号），

当循环使得i超过65535时，则i会返回0重新开始计数

如i=65534，当i+=3时，i=1

其实就是 i=(65534+3)%(2^16)=1

一元同余方程求解，假设算法恰好执行了X步，则A+CX ≡B(mod M)，其中M=1<<k.将其变形后，用扩展欧几里得算法求解。

#include<cstdio> #include<iostream> #include<cstring> using namespace std; 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 ans=exgcd(b,a%b,x,y); long long temp=x; x=y; y=temp-a/b*y; return ans; } int main() { long long a,b,c,k; long long x,y; while(scanf("%lld%lld%lld%lld",&a,&b,&c,&k)!=EOF) { if(a==0&&b==0&&c==0&&k==0) break; long long M=1<<k; long long g=exgcd(c,M,x,y);///求未知数前的系数的最大公因数 if((b-a)%g!=0) cout<<"FOREVER"<<endl; else { long long ans=x*(b-a)/g; long long temp=M/g; ans=(ans%temp+temp)%temp; cout<<ans<<endl; } } return 0; }