引入
常想起在空间里见过的一些智力题，这个题你见过吗：
一堆苹果，$3$个$3$个地取剩$1$个，$5$个$5$个地取剩$1$个，$7$个$7$个地取剩$2$个，苹果最少有几个？
够焦头烂额的（雾
大力算可知至少有16个。
我们把它抽象成数学问题：
求满足
(egin{cases}xequiv1pmod{3}\xequiv1pmod{5}\xequiv2pmod{7}end{cases})
的最小正整数$x$。
感性地猜到有一个长为$3×5×7=105$的循环节，至于为啥，一会就知道了。
求解
(下面是老祖宗神奇的思维，别问我为什么)
构造方程组：
(egin{cases}xequiv0pmod{3}\xequiv0pmod{5}\xequiv1pmod{7}end{cases})
显然这里$x$可表示为$15y(yin Z)$，即：
$$15yequiv1pmod{7}$$
可得（不就是乘法逆元吗？）：
$$15yequiv1pmod{7} xrightarrowyequiv1pmod{7}xrightarrowy_=1xrightarrowx_=15$$
同理构造三个方程，解((x))分别为：$15,70,21$。
再乘上余数即可（记得取模）：
(ans=15×2+70×1+21×1=121equiv16pmod{3×5×7=105})
最后的答案即为同余号右边的数。
这样可以用代码实现：
题目链接：P1495 【模板】中国剩余定理(CRT)/曹冲养猪
(Code):
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int n;
ll a[15],b[15];
ll sum=1,now=1,ans=0,rt=1;
ll x,y;
inline void exgcd(ll a,ll b)
{
if(b==0)
{
x=1,y=0;
return;
}
exgcd(b,a%b);
ll t=x;
x=y;
y=t-a/b*y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++) rt=rt*a[i];
for(int i=1;i<=n;i++)
{
sum=now=1;
for(int j=1;j<=n;j++) if(i!=j) now=now*a[j],sum=sum*a[j]%a[i];
exgcd(sum,a[i]);
x=(x%a[i]+a[i])%a[i];
ans=(ans+b[i]*x*now)%rt;
}
printf("%lld
",ans);
return 0;
}
复杂度是$O(n^2+nlogn)$，对于此题$n=10$的数据，足以。
优化
有什么更好的方法？
用$n-1$次中国剩余定理！
其实就是。
看样例：
我们先求解：
(egin{cases}xequiv1pmod{3}\xequiv1pmod{5}end{cases})
我们知道，最后的得数还是同余方程，比如上边样例得出的：
(xequiv16pmod{105})
这类似一个合并过程，我们把两个方程合并成一个即可，如：
(egin{cases}xequiv1pmod{3}\xequiv1pmod{5}end{cases})
可合并为：
(xequiv8pmod{15})
再与下一个方程合并即可，这样的合并仅是$O(2logn)$的，不过似乎正解是$O(logn)$，差不多了......
(Code):
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int n;
struct node
{
ll a,b;
}e[15];
ll sum=1,now=1,ans=0,rt=1;
ll x,y;
inline void exgcd(ll a,ll b)
{
if(b==0)
{
x=1,y=0;
return;
}
exgcd(b,a%b);
ll t=x;
x=y;
y=t-a/b*y;
}
node merge(node m,node n)
{
node ans;
ans.a=m.a*n.a;
exgcd(n.a%m.a,m.a);
ll l=(x%m.a+m.a)%m.a;
l=l*m.b%ans.a*n.a%ans.a;
exgcd(m.a%n.a,n.a);
ll r=(x%n.a+n.a)%n.a;
r=r*n.b%ans.a*m.a%ans.a;
ans.b=(l+r)%ans.a;
return ans;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&e[i].a,&e[i].b);
node o=e[1];
for(int i=2;i<=n;i++) o=merge(o,e[i]);
printf("%lld
",o.b);
return 0;
}
不过码量大一些，我想这么小的数据就不必了吧。
（这一部分在题解区没有，不想放上）
(upd:2020.2.29( ext{真是特别的一天(其实我妈并不赞同我今晚颓电脑，不过还是完成二月的任务吧)}))
我不会告诉你上述做法有锅的
所以给你一组数据：戳我
使用中国剩余定理是有前提的，就是模数必须互质。
都错了，傻眼了吧（不要怀疑数据）
老祖宗太不认真了，
你不能这样质疑，因为他们发现并补救了：
拓展中国剩余定理
题目链接：P4777 【模板】扩展中国剩余定理（EXCRT）
看某大佬博客懵逼许久，终于在挑战程序设计竞赛（第2版）
找到了答案（当然我是在纸质书上看的）
比如说样例：
我们以先前的合并思想，对前两个合并：
样例：
(egin{cases}xequiv6pmod{11}\xequiv9pmod{25}\xequiv17pmod{33}end{cases})
对前两个：
(egin{cases}xequiv6pmod{11}\xequiv9pmod{25}end{cases})
易得：
(x=11t+6(tin Z))
带进去就万事大吉了：
$$11t+6equiv9pmod{25}$$
化简
$$11tequiv3pmod{25}$$
不得不说你该会解吧,易得：
(t_{min}=23)
答案的处理
其实你会反代的对不对？
(x=11×23+6=259equiv259pmod{lcm(11 ,25)=275})
这样就好了，一一合并即可。
复杂度是$O(nlog n)$,可以通过本题。
(Code):
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=100005;
typedef long long ll;
inline long long mul(long long x,long long y,long long mod)
{
long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
return tmp<0 ? tmp+mod : tmp;
}
struct node
{
ll n,m;//m是模数，n是余数
}a[MAXN];
ll x,y,ans=1;
void exgcd(ll a,ll b)
{
if(b==0)
{
x=1,y=0;
return;
}
exgcd(b,a%b);
ll t=x;
x=y;
y=t-a/b*y;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll solve(ll a,ll b,ll c)
{
ll g=gcd(a,b);
if(c%g!=0) return -1;
a/=g,b/=g,c/=g;
exgcd(a,b);
x=x*c;
x=(x%b+b)%b;
return x;
}
node merge(node x,node y)
{
node ans;
ans.m=(x.m/gcd(x.m,y.m))*y.m;
ll t=solve(x.m,y.m,(y.n+y.m-x.n)%y.m);
if(t<0)
{
ans.n=-1;
return ans;
}
ans.n=mul(t,x.m,ans.m);
ans.n=(ans.n+x.n)%ans.m;
return ans;
}
ll n;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].m,&a[i].n);
node rt=a[1];
for(int i=2;i<=n;i++)
{
rt=merge(rt,a[i]);
if(rt.n<0)
{
printf("-1
");
return 0;
}
}
printf("%lld
",rt.n);
return 0;
}
这个代码是会$WA$一个点被卡精度的的，不过大力快速乘（不懂大佬的方法）或是__int128并没什么意义，于是就......