大數(shù)取模
ll ans=0; for(int i=0; i<strlen(s); i++) { ans=(ans*10+s[i]-'0')%mod; }
快速冪
- 計算一個數(shù)
的
次冪即
快速冪的思想就是將指數(shù)
其中指數(shù),所以我們可以求出
按照循環(huán)要循環(huán)
次，現(xiàn)在只要計算
次,所以快速冪的時間復雜度是
)
long long power(int a,int n) { long long ans=1; long long base=a; while(n) { if(n&1) { ans=ans*base; } base=base*base; n>>=1; } return ans; }
歐幾里得
- 求最大公約數(shù)
long long gcd(long long a,long long b) { if(b==0) { return a; } else { return gcd(b,a%b); } }
- 最小公倍數(shù)
擴展歐幾里得
- 對于不完全為
的非負整數(shù)
表示
的最大公約數(shù)括饶，必然存在整數(shù)對
, 使得
.
證明
- ①：
立即推
②：
設(shè)
設(shè)
已知：(歐幾里得)
立即推
可得：;
%20*%20y2%20%3B)
define ll long longvoid exgcd(ll a,ll b,ll &gcd,ll &x,ll &y) { if(b==0) { x=1; y=0; gcd=a; } else { exgcd(b,a%b,gcd,y,x); y-=x*(a/b); } }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,y,x); y-=x*(a/b); return r; }
逆元
對于正整數(shù)
（即），那么把這個同余方程中的最小正整數(shù)解
叫做
的逆元。
逆元用途
如何求解植康，取模運算中
在這種情況下就要求在模
的情況下的逆元
了
即,
然后逆元求法
①.費馬小定理
假如質(zhì)數(shù)且那么
因為根據(jù)費馬小定理可知
所以
②.擴展歐幾里得算法
擴展歐幾里得(互質(zhì) 瞧壮，且
求解
解出的最小正整數(shù)解ll inv ( ll a , ll b ) { ll gcd, x, y; exgcd(a, b, gcd, x, y); return gcd == 1 ? ( x % b + b ) % b : -1 ; // x 可能為負數(shù) }
中國剩余定理
其中兩兩互質(zhì)的整數(shù)
結(jié)論：
其中
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int mm=1e6+10; ll c[mm],mod[mm]; ll exgcd(ll a,ll b,ll &gcd,ll &x,ll &y) { if(b==0) { x=1; y=0; gcd=a; } else { exgcd(b,a%b,gcd,y,x); y-=x*(a/b); } } ll inv(ll a,ll b) { ll gcd,x,y; exgcd(a,b,gcd,x,y); return gcd==1?(x%b+b)%b:-1; } int main( ) { int n; while(~scanf("%d",&n)) { ll ans=1; for(int i=1; i<=n; i++) { scanf("%lld%lld",&mod[i],&c[i]); ans*=mod[i]; } ll sum=0; for(int i=1; i<=n; i++) { ll a=ans/mod[i]; ll b=mod[i]; sum=(sum+c[i]*a*inv(a,b)%ans)%ans; } printf("%lld\n",sum); } return 0; }
擴展中國剩余定理
其中
令
根據(jù)擴展歐幾里得算法求解,滿足
則
實際上有多組解
取
的最小整數(shù)解莉恼，
最后合成void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y) { if(b==0) { x=1; y=0; gcd=a; } else { exgcd(b,a%b,gcd,y,x); y-=x*(a/b); } } ll mul(ll a,ll n,ll m)//快速乘 { ll ans=0; ll base=a; while(n) { if(n&1) { ans=(ans+base)%m; } base=(base+base)%m; n>>=1; } return ans%m; } ll excrt(int n) { ll x,y,gcd; ll M=1,ans=0;//k數(shù)組是被模數(shù)，mod數(shù)組是模數(shù)赊级，k%mod for(int i=1;i<=n;i++) { ll a=M; ll b=mod[i]; ll c=(k[i]-ans%b+b)%b; exgcd(a,b,gcd,x,y); if(c%gcd!=0) { return -1; } ll t=b/gcd; x=mul(x,c/gcd,t); ans+=x*M;//更新前i個方程組的答案 M*=t;//前i個modi的小公倍數(shù) ans=(ans%M+M)%M; } return (ans%M+M)%M; }
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int MAX=1e5+10;
ll k[MAX],mod[MAX];//mod數(shù)組是模數(shù),k數(shù)組是被模數(shù)-->>k%mod
void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
gcd=a;
}
else
{
exgcd(b,a%b,gcd,y,x);
y-=x*(a/b);
}
}
ll mul(ll a,ll n,ll m)
{
ll ans=0;
ll base=a;
while(n)
{
if(n&1)
{
ans=(ans+base)%m;
}
base=(base+base)%m;
n>>=1;
}
return ans%m;
}
ll excrt(int n)
{
ll x,y,gcd;
ll M=1,ans=0;
for(int i=1; i<=n; i++)
{
ll a=M;
ll b=mod[i];
ll c=(k[i]-ans%b+b)%b;
exgcd(a,b,gcd,x,y);
if(c%gcd!=0)
{
return -1;
}
ll t=b/gcd;
x=mul(x,c/gcd,t);
ans+=x*M;
M*=t;
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
int main( )
{
int n;
while(~scanf("%d",&n))
{
for(int i=1; i<=n; i++)
{
scanf("%lld%lld",&mod[i],&k[i]);
}
printf("%lld\n",excrt(n));
}
return 0;
}
