中国剩余定理 & 扩展中国剩余定理
题目 ： TJOI2009猜数字（https://www.luogu.org/problem/P3868）
分析 ：裸中国剩余定理 ， 坑的是最后一个点爆longlong ，需要加快速乘 。 计算逆元之后转化为正整数，负数就T了
code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[12],b[12],mod=1;
ll ksmul(ll a,ll b)
{
ll ans=0;
while(b)
{
if(b&1) ans=(ans+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return ans;
}
void ex_gcd(ll a,ll b,ll &x,ll &y)
{
if(b==0) {
x=1,y=0; return;
}
ex_gcd(b,a%b,x,y);
ll t=x;
x=y,y=t-a/b*y;
}
void CRT(int n)
{
ll ans=0,Mi,x,y;
for(int i=1;i<=n;i++) {
Mi=mod/b[i];
ex_gcd(Mi,b[i],x,y);
x=(x%b[i]+b[i])%b[i];
ans=(ans+ksmul(ksmul(a[i],x),Mi)+mod)%mod;
}
printf("%lld",ans);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) {
scanf("%lld",&b[i]);
mod*=b[i];
}
CRT(n);
return 0;
} 题目 ：扩展CRT板子 (https://www.luogu.org/problem/P4777)
code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 3;
ll a[maxn],b[maxn];
ll ksmul(ll a,ll b,ll mod)
{
ll ans=0;
while(b)
{
if(b&1) ans=(ans+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return ans;
}
void ex_gcd(ll a,ll b,ll &x,ll &y,ll &gcd)
{
if(b==0) {
x=1,y=0,gcd=a; return;
}
ex_gcd(b,a%b,x,y,gcd);
ll t=x;
x=y,y=t-a/b*y;
}
ll EX_CRT(int n)
{
ll ans=b[1],M=a[1],x,y,c,gcd;
for(int i=2;i<=n;i++) {
c=(b[i]-ans%a[i]+a[i])%a[i];
ex_gcd(M,a[i],x,y,gcd);
if(c%gcd) return -1;
x=ksmul(x,c/gcd,a[i]/gcd);
ans+=x*M;
M*=a[i]/gcd;
ans=(ans%M+M)%M;
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]);
printf("%lld",EX_CRT(n));
return 0;
} 
小马智行一面3人在聊
查看4道真题和解析