同余问题（一本通）

1631：【例 1】青蛙的约会

(x+mt)=(y+nt) mod l
//(x+mt)-(y+nt)=kl (x-y)+(m-n)t=kl 转化为 (m-n)t+kl=y-x t和k未知
//如果gcd(m-n,l)能够整除y-x那么就有解

下面的代码常用：

之后要用通解公式 x=x1+b/r*t , y=y1-a/r*t
LL xx=0,yy=0;
extend_gcd(a,b,xx,yy);
xx=xx*c/r; //x0*c/gcd
LL temp=b/r; //b/gcd
xx=(xx>=0)? (xx%temp):(xx%temp+temp);
printf("%lld ",xx);

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
LL x,y,m,n,l;
//(x+mt)=(y+nt) mod l
//(x+mt)-(y+nt)=kl  (x-y)+(m-n)t=kl  转化为  (m-n)t+kl=y-x t和k未知
//如果gcd(m-n,l)能够整除y-x那么就有解
LL gcd(LL a,LL b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
void extend_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1;y=0;return;
    }
    extend_gcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-(a/b)*y;
}
int main(){
    /*
    x+T*m = y+T*n  (%L)
  -->x-y = T*(n-m)+k*L
  -->T*(n-m)+k*L = x-y 类似(ax+by=c的形式)
  如果(x-y)%gcd(n-m,L)!=0无解
    */
    cin>>x>>y>>m>>n>>l;
    LL a=n-m;
    LL b=l;
    LL c=x-y;
    LL r=gcd(a,b);
    if(a<0){
        a=-a;
        c=-c;
    }
    if(c%r){
        printf("Impossible");
        return 0;
    } 
    //之后要用通解公式 x=x1+b/r*t , y=y1-a/r*t 
    LL xx=0,yy=0;
    extend_gcd(a,b,xx,yy);
    xx=xx*c/r;  //x0*c/gcd
    LL temp=b/r;  //b/gcd
    xx=(xx>=0)? (xx%temp):(xx%temp+temp);
    printf("%lld
",xx);
return 0;
}

View Code

1632：【例 2】[NOIP2012]同余方程

求关于 $x$

模板：

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//这个就是模板了吧
LL a,b;
//求 ax=1(mod b) 的最小正整数解
//ax-1=by---ax+by=1  gcd(a,b)=1 互素
void extend_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1;y=0;return;
    }
    extend_gcd(b,a%b,x,y);
    LL tmp=x;
    x=y;
    y=tmp-(a/b)*y;
} 
LL gcd(LL a,LL b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
int main(){
    cin>>a>>b;
    LL r=gcd(a,b);
    LL temp=b/r;
    LL  xx=0,yy=0;
    extend_gcd(a,b,xx,yy);
    //因为是1，所以不用xx*c/gcd 
    xx=(xx%temp+temp)%temp;
    cout<<xx<<endl;
return 0;
}

View Code

1633：【例 3】Sumdiv

求出A的约数之和，然后需要全部都乘以B

对于一个数
如果他是p1a1*p1a2*p3a3*~~*pnan
那么他的因数和就是（p10+p11+p12+...+p1a1）*（p20+p21+...+p2a2）*...*（pn1+pn2+...+pnan）
于是这道题就是要把所有质因数的幂次的乘积，先来推一下等比公式
令 S = p0+p1+p2+...+pa，（1）
则p*S = p1+p2+...+pa+pa+1，（2）
（2）-（1）可以得到 S*(p-1) = pa+1-p0，所以S= （pa+1-p0）/ (p-1) ，前面一项显然Ksm就可以解决，考虑后一项
需要用到p-1的逆元，如何求呢？
定义一个数a（就求a的逆元
对于任意一个数 X/a ≡ X*Inva (%Mod)
易知 a*Inva ≡ 1 (%Mod)
随便推导下
原式: a*Inva = 1 (%Mod)
--> a*Inva-k*Mod = 1 (%Mod)
--> a*Inva+P*Mod = 1 (%Mod) (类ax+by=c的形式)

/*
原式: a*Inva = 1 (%Mod)
  --> a*Inva-k*Mod = 1 (%Mod)
  --> a*Inva+P*Mod = 1 (%Mod) (类ax+by=c的形式)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const ll Mod=9901;
ll A,B;
int cnt=0;
struct Prime
{
    ll Shuz,Xis;
}Prim[50];
inline ll Ksm(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1)
        {
            ans=ans*x%Mod;
        }
        x=x*x%Mod;
        y>>=1;
    }
    return ans;
}
ll gcd(ll x,ll y)
{
    return (!y)?(x):(gcd(y,x%y));
}
inline void Exgcd(ll a,ll b,ll &X,ll &Y)
{
    if(b==0)
    {
        X=1;
        Y=0;
        return;
    }
    Exgcd(b,a%b,X,Y);
    ll XX=X,YY=Y;
    X=YY;
    Y=XX-a/b*YY;
    return;
}
//a*Inva+Mod*k = 1 (%Mod)
inline ll Inv(ll Num)
{
    ll a,b,c,r,X,Y;
    a=Num;
    b=Mod;
    c=1;
    r=gcd(a,b);
    Exgcd(a,b,X=0,Y=0);
    X=X*r/c;
    ll tmp=b/r;
    X=(X>=0)?(X%tmp):(X%tmp+tmp);
//    printf("X=%lld Test=%lld
",X,Num*X%Mod);
    return X;
}
inline void Solve(ll Num)
{
    int i;
    for(i=2;i<=sqrt(Num);i++)
    {
        if(Num%i==0)
        {
            Prim[++cnt].Shuz=i;
            Prim[cnt].Xis=0;
            while(Num%i==0)
            {
                Prim[cnt].Xis++;
                Num/=i;
            }
            Prim[cnt].Xis*=B;
        }
    }
    if(Num>1)
    {
        Prim[++cnt]=(Prime){Num,B};
    }
    return;
}
int main()
{
    int i;
    ll ans=1ll;
    R(A); R(B);
    Solve(A);
    for(i=1;i<=cnt;i++)
    {
//        printf("%lld %lld
",Prim[i].Shuz,Prim[i].Xis);
        ll tmp=(Ksm(Prim[i].Shuz,Prim[i].Xis+1)-1+Mod)%Mod;
        tmp=tmp*Inv(Prim[i].Shuz-1)%Mod;
        ans=ans*tmp%Mod;
    }
    Wl(ans);
    return 0;
}

View Code

1634：【例 4】曹冲养猪

中国剩余定理（孙子定理）

https://www.cnblogs.com/wkfvawl/p/9633188.html

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
LL n;
//中国剩余定理（孙子定理）
//https://www.cnblogs.com/wkfvawl/p/9633188.html 
LL aa[12],bb[12];
void extend_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1;
        y=0;return;
    }
    extend_gcd(b,a%b,x,y);
    LL tmp=x;
    x=y;
    y=tmp-(a/b)*y;
} 
LL gcd(LL x,LL y){
    if(y==0) return x;
    else return gcd(y,x%y);
}

int main(){
    scanf("%lld",&n);
    
    LL mod=1;
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&aa[i],&bb[i]);
        mod*=aa[i];
    } 
    LL ans=0;
    LL x,y;
    for(int i=1;i<=n;i++){
        LL p=mod/aa[i];
        extend_gcd(p,aa[i],x,y);
        //cout<<x<<endl;
        ans=(ans+bb[i]*x*p)%mod;
    }
    cout<<(ans+mod)%mod;
    /*   超时到怀疑人生哈哈哈哈 
    for(LL i=mm;;i++){
        bool flag=0;
        for(int j=1;j<=n;j++){
            if(!judge(i-bb[j],aa[j])) {
                flag=1;break;
            }
        }
        if(!flag){
            cout<<i<<endl;break;
        }
    }
    */
return 0;
}

View Code

1635：【例 5】Strange Way to Express Integers

变形是需要判断有没有解
//中国剩余定理的要求就是：m1,m2....mn两两互素
//但是如果不是两两互素的话，那么就需要扩展中国剩余定理
//https://www.cnblogs.com/zwfymqz/p/8425731.html

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1e5+10;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//变形是需要判断有没有解
//中国剩余定理的要求就是：m1,m2....mn两两互素
//但是如果不是两两互素的话，那么就需要扩展中国剩余定理
//https://www.cnblogs.com/zwfymqz/p/8425731.html 
LL n;
//x=c1(mod m1)
LL c[maxn],m[maxn],x,y;
LL gcd(LL a,LL b){
    if(b==0) return a;
    return gcd(b,a%b);
}
LL extend_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1;y=0;return a;
    }
    LL r=extend_gcd(b,a%b,x,y);
    LL tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return r;
}
LL inv(LL a,LL b){  //a在模b下的逆
    LL r=extend_gcd(a,b,x,y); 
    while(x<0) x+=b; //取最小非负的逆 
    return x;
} 
int main(){
    while(~scanf("%lld",&n)){
        for(int i=1;i<=n;i++){
            scanf("%lld %lld",&m[i],&c[i]);
        }
        bool flag=0;
        for(int i=2;i<=n;i++){  //两两合并位1个，并继续扩展 
            LL m1=m[i-1],m2=m[i];
            LL c1=c[i-1],c2=c[i];
            LL t=gcd(m1,m2);
            if((c2-c1)%t!=0){
                flag=1;break;  //必须余数为0 因为式子中要出现相除 
            }
            m[i]=(m1*m2)/t;
            c[i]=(inv(m1/t,m2/t)*(c2-c1)/t)%(m2/t)*m1+c1;
            c[i]=(c[i]%m[i]+m[i])%m[i];
        }
        printf("%lld
",flag? -1:c[n]);
    }
return 0;
}

View Code

1636：【例 6】计算器

三种计算

第一种，就是快速幂

第二种，就是同余公式的运用

第三种，高次同余方程

BSGS可以解决高次同余方程：
//https://www.cnblogs.com/kamimxr/p/11555986.html

用map存储，具体百度

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//1.y^zmod p
//2. x*y=z(mod p)
//3. y^x=z(mod p)

LL   js1(LL y,LL z,LL p){
    LL tmp=1;
    while(z){
        if(z&1) tmp=tmp*y%p;
        y=y*y%p;
        z>>=1;
    }
    return tmp%p;
}
void extend_gcd(LL a,LL b,LL &x,LL &y){
        if(b==0){
        x=1;
        y=0;return;
    }
    extend_gcd(b,a%b,x,y);
    LL tmp=x;
    x=y;
    y=tmp-(a/b)*y;
}
LL gcd(LL a,LL b){
    if(b==0 ) return a;
    else return gcd(b,a%b);
}
//x*y=z(mod p)  ax=b(mod m)
//ax+my=b
//y*x+p*k=z  已知y,p,z 
//求出x0之后
//最小非负解：((x=x0*z/gcd)+p/gcd)%(p/gcd)
void js2(LL y,LL z,LL p){
    LL A=y,B=z,M=p;
    LL xx,yy;
    extend_gcd(A,M,xx,yy);
    //gcd(a,m)%b==0
    LL d=gcd(y,p);
    if(z%d){
        printf("Orz, I cannot find x!
");return;
    }
    xx=((xx*z/d)%(p/d)+p/d)%(p/d);
    printf("%lld
",xx);
    //return (xx%M+M)%M;
}
//y^x=z(mod p)
//BSGS可以解决高次同余方程：
//https://www.cnblogs.com/kamimxr/p/11555986.html

void js3(LL a,LL ans,LL p){
    map<LL,LL> myhash;
    ans%=p;
    int tmp=sqrt(p)+1;
    for(int i=0;i<tmp;i++){
        //js1其实就是快速幂 
        myhash[(ans)*js1(a,i,p)%p]=i;
    }
    a=js1(a,tmp,p)%p;
    if(a==0&&ans==0){
        printf("1
");return;
    }
    if(a==0&&ans!=0){
        printf("Orz, I cannot find x!
");
        return;
    }
    for(int i=0;i<=tmp;i++){
        if(myhash.find(js1(a,i,p))!=myhash.end()&&(i*tmp-myhash[js1(a,i,p)]>=0)){
            printf("%d
",i*tmp-myhash[js1(a,i,p)]);
            return;
        }
    }
    printf("Orz, I cannot find x!
");
} 
int main(){
    int t,k;
    LL y,z,p;
    while(~scanf("%d %d",&t,&k)){
        if(k==1){
            for(int i=1;i<=t;i++){
                scanf("%lld %lld %lld",&y,&z,&p);
                printf("%lld
",js1(y,z,p));
            }
        }
        else if(k==2){
            for(int i=1;i<=t;i++){
                scanf("%lld %lld %lld",&y,&z,&p);
                js2(y,z,p);
            }
        }
        else if(k==3){
            ////y^x=z(mod p)
            for(int i=1;i<=t;i++){
                scanf("%lld %lld %lld",&y,&z,&p);
                js3(y,z,p);
            }
        }
    }
return 0;
}

View Code

1637：荒岛野人

//和前面两道中国剩余定理不同的是，这个是每一年的余数都不能相同
//其实我一开始想的也是暴力，但是换一种暴力的思路
//要使得每一年还活着的野人居住的地方都不一样，就可以转化为思考住在一起的方程没有解或者解不符合条件
/*
以有野人的居住的山洞的最大编号作为初始的山洞数，从这里开始搜索：如果此时的山洞数符合条件就直接输出，否则山洞数加一。至于判断的过程，就是很暴力的枚举任意两个野人。
我们假设经过若干年后有两个野人处在了同一个山洞中，设i,j为野人编号，m为此时判断的山洞数，x为经过了多少年。那么就很容易得到
c[i]+x*p[i]≡c[j]+x*p[j](mod m)
稍稍变形得
(p[i]-p[j])*x≡c[j]-c[i](mod m)
那这不就是一个简单的线性同余方程嘛！
接下来就好办多了，用拓展欧几里得算法解出x，若无解（即c[j]-c[i]不是gcd(p[i]-p[j],m)的整数倍），那就说明这个山洞数满足“没有任何两个野人处在同一个山洞中”的条件，继续枚举其
他野人；若有解，那还要再分两种情况：
解得的x>min(l[i],l[j])，即此时两个野人至少已经die了一个了，那么活野人和死野人处不处在同一个山洞已经无所谓了，不碍事，继续枚举！
解得的x<=min(l[i],l[j])，那没办法，两个野人都活着，却还处在同一个山洞里，说明这个山洞数不符题意，直接返回false。
然鹅这道题还不能就这样轻易的AC掉，注意：由于p[i]-p[j]有可能为负，所以gcd(p[i]-p[j],m)也有可能为负，那么在拓展欧几里得算法中求解x时，一定要注意将m/(gcd(m,p[i]-p[j]))
带上abs()！
https://blog.csdn.net/anglanjing7414/article/details/101189720

！还是要注意细节：要考虑如果有解的情况下，求出来的值x有没有超过寿命，还有负数问题

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//和前面两道中国剩余定理不同的是，这个是每一年的余数都不能相同
//其实我一开始想的也是暴力，但是换一种暴力的思路
//要使得每一年还活着的野人居住的地方都不一样，就可以转化为思考住在一起的方程没有解或者解不符合条件

int n;
int c[20],p[20],l[20];
//初始位置、移动、寿命
int gcd(int x,int y){
	if(y==0) return x;
	else return gcd(y,x%y);
}
void exgcd(int a,int b,int &d,int &x,int &y){ //顺带求出了最大公约数 
	if(b==0){
		x=1;y=0;d=a;return;
	}
	exgcd(b,a%b,d,x,y);
	int tmp=x;
	x=y;
	y=tmp-(a/b)*y;
	return;
}
bool judge(int m){
	//(p[i]-p[j])*x≡c[j]-c[i](mod m)
	int a,b,cc,x,y,d;
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			 a=p[i]-p[j];
			 b=m;
			 cc=c[j]-c[i];
			 if(cc%gcd(a,b)!=0) continue; //无解
			 exgcd(a,b,d,x,y);  //d=gcd(a,b)
			 int t=abs(b/d);
			 //要保证t是正数 
			 x=((x*cc/d)%t+t)%t;
			 if(x<=min(l[i],l[j])) return false;
		}
	}
	return true;
}
int main(){
	int maxx=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d %d",&c[i],&p[i],&l[i]);
		maxx=max(maxx,c[i]);
	}
	for(int i=maxx;;i++){
		if(judge(i)){
			printf("%d
",i);
			break;
		}
	}
return 0;
}

1638：五指山

模板题

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
int t;
LL n,d,x,y;
//(dt+x)%n=y   dt+mn=y-x
//a=d  b=n c=y-x
LL gcd(LL x,LL y){
	if(y==0) return x;
	else return gcd(y,x%y);
}
void exgcd(LL a,LL b,LL &xx,LL &yy){
	if(b==0){
		xx=1;yy=0;return;
	}
	exgcd(b,a%b,xx,yy);
	LL tmp=xx;
	xx=yy;
	yy=tmp-(a/b)*yy;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%lld %lld %lld %lld",&n,&d,&x,&y);
		//x%=n;
		//y%=n;
		LL a=d,b=n,c=y-x;
		LL r=gcd(a,b);
		LL tmp=b/r;
		if(c%r){
			printf("Impossible
");continue;
		}
		LL xx,yy;
		exgcd(a,b,xx=0,yy=0);
		
		xx=(xx*c)/r;
		xx=(xx%tmp+tmp)%tmp;
		printf("%lld
",xx);
	}
	
return 0;
}

1639：Biorhythms

其实就是中国剩余定理的应用，求通解

这道题有些细节：特列输出，还有如果结果还小于d，那么累加的是23*28*33

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//这个应该就是中国剩余定理了吧
//但是结果计算，通解？ 
int mm[4]={23,28,33};
int aa[4];
int p,e,i,d;
int op=0;
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;y=0;return;
	}
	exgcd(b,a%b,x,y);
	int tmp=x;
	x=y;
	y=tmp-(a/b)*y;
}
void crt(){
	int m=1,ans=0,t,x,y;
	m=23*28*33;
	
	for(int i=0;i<3;i++){
		t=m/mm[i];
		exgcd(t,mm[i],x=0,y=0);
		ans=(ans+aa[i]*x*t)%m;
	}
	while(ans<=d){   //如果这样的结果还小于d，那么累加的是23*28*33 
		ans+=m;
	}
	ans=ans-d;
	printf("Case %d: the next triple peak occurs in %d days.
",++op,ans);
}
int main(){
	while(~scanf("%d %d %d %d",&aa[0],&aa[1],&aa[2],&d)){
		if(aa[0]==-1&&aa[1]==-1&&aa[2]==-1&&d==-1) break;
		if(aa[0]==0&&aa[1]==0&&aa[2]==0&&d==0){
			printf("Case %d: the next triple peak occurs in 21252 days.
",++op);   //特列 
			continue; 
		}
		crt();
	}
return 0;
}

1640：C Looooops

要理解这个k位存储系统的意思！！！！---->mod=2^k 这个意思

所以分析最重要，分析出来其实就是模板题

(A+k*C)%MOD=B;
A+C*p1 = B (%Mod) Mod=2^k
C*p1+Mod*p2 = B-A (类ax+by=c的形式)
求p1

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//模板题
//(A+k*C)%MOD=B;
/*
A+C*p1 = B (%Mod) Mod=2^k
C*p1+Mod*p2 = B-A (类ax+by=c的形式)
求p1
*/ 
LL A,B,C,k;
LL gcd(LL x,LL y){
	if(y==0) return x;
	else return gcd(y,x%y);
}
void exgcd(LL a,LL b,LL &x,LL &y){
	if(b==0){
		x=1;y=0;return;
	}
	exgcd(b,a%b,x,y);
	LL tmp=x;
	x=y;
	y=tmp-(a/b)*y;
	return;
}
int main(){
	while(~scanf("%lld %lld %lld %lld",&A,&B,&C,&k)){
		if(A==0&&B==0&&C==0&&k==0) break;
		LL mod=1LL<<k;
		LL a,b,c,r,x,y,tmp;
		a=C;b=mod;c=B-A;
		r=gcd(a,b);
		tmp=b/r;
		if(c%r){
			printf("FOREVER
");
			continue;
		}
		exgcd(a,b,x=0,y=0);
		x=x*c/r;
		x=(x>=0)? (x%tmp):(x%tmp+tmp);
		printf("%lld
",x);
	}
return 0;
}