中国剩余定理
问题：
对于方程组
\(x \equiv b_1 (\bmod\) \(p_1)\)
\(x \equiv b_2 (\bmod\) \(p_2)\)
……
\(x \equiv b_n (\bmod\) \(p_n)\)
满足任意 \(\gcd(p_i,p_j)=1\)
求解\(x\) 的最小正整数解
思路：
设 \(mul=p_1\times p_2 \times ... \times p_n\)
从\(1\)~\(n\)枚举 \(p_i\) , 求解 \(mul/p_i\) 模 \(p_i\) 意义下的逆元 \(y_i\)
则 \(x=\sum_{i=1}^n (y_i\times b_i\times mul/p_i)\bmod mul\)
证明：
对于每一个 \(y_i\) 满足 \(y_i\times mul /p_i \equiv 1 (\bmod\) \(p_i )\)
所以 \(b_i\times y_i\times mul /p_i \equiv b_i (\bmod\) \(p_i )\)
且 \(b_i\times y_i\times mul /p_i \equiv 0 (\bmod\) \(mul/p_i)\)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=15;
int n,a[N],b[N];
LL x,y;
inline int read()
{
register int x=0;
char c=getchar();
while(c<'0'||c>'9'){
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x;
}
int exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b){
x=1,y=0;
return a;
}
LL res=exgcd(b,a%b,x,y);
LL t=x;x=y;y=t-a/b*y;
return res;
}
LL crt()
{
LL m=1,res=0;
for(int i=1;i<=n;i++)m*=a[i];
for(int i=1;i<=n;i++){
LL s=m/a[i];
exgcd(s,a[i],x,y);
res=(res+s*b[i]*x)%m;
}
return (res+m)%m;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)a[i]=read(),b[i]=read();
printf("%lld\n",crt());
return 0;
}
拓展中国剩余定理
对于方程组
\(x \equiv b_1 (\bmod\) \(p_1)\)
\(x \equiv b_2 (\bmod\) \(p_2)\)
……
\(x \equiv b_n (\bmod\) \(p_n)\)
求解\(x\) 的最小正整数解
与前面不同的是，\(p\) 能任意取值
考虑每次将两个方程合并成一个，直至得出答案
合并：
设有两个方程：
\(x\equiv r_1 (\bmod \ m_1)\)
\(x\equiv r_2 (\bmod \ m_2)\)
则 \(x=k_1m_1+r_1=-k_2m_2+r_2\) ( \(k_1,k_2\) 为整数)
所以 \(k_1m_1+k_2m_2=r_2-r_1\)
用拓展欧几里得求出 \(k_1\) ,得到方程的一个特解 \(x_0=k_1m_1+r_1\)
通解 \(k_i=k_1+ u\times\frac{ m_2}{\gcd(m_1,m_2)}\)
则 \(k_im_1+r_1=k_1m_1+r_1+u\times \frac{m_1m_2}{\gcd(m_1,m_2)}\)
通解 \(x=x_0+ u\times lcm(m_1,m_2)\)
所以合并为方程：
\(x\equiv x_0(\bmod \ lcm(m_1,m_2))\)
代码：
#include<bits/stdc++.h>
#define int __int128 //__int128 要手写快读、快写
using namespace std;
typedef long long LL;
const int N=100010;
LL n,a[N],b[N];
int x,y,_A,_B,A,B;
inline int read()
{
register int x=0,f=1;
char c=getchar();
while(c<'0'&&c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
inline void print(int x)
{
if(x<0){
putchar('-');
x=-x;
}
if(x>9)print(x/10);
putchar(x%10+'0');
}
int exgcd(int a,int b,int &x,int &y)
{
if(!b){
x=1,y=0;
return a;
}
int res=exgcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
return res;
}
signed main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
_A=a[1],_B=b[1];
for(int i=2;i<=n;i++){//合并
int m1=_A,m2=a[i],r1=_B,r2=b[i];
int d=exgcd(m1,m2,x,y);
x=(int)x*(r2-r1)/d;
A=(int)m1*m2/d;
B=(int)x*m1+r1;
B=(B%A+A)%A;//将B转化为正数
_A=A,_B=B;
}
print(B);
cout<<endl;
return 0;
}
欧拉定理
欧拉函数：
\(\varphi(i)\): 是 \([1,n)\) 中与n互素的正整数（包括 \(1\) ）的个数，\(n\) 为正整数
\(\varphi(1)=1\)
若 \(p\)为质数，则 \(\varphi(p)=p-1\), \(\varphi(p^k)=p^k-p^{k-1}\)
（与 \(p\) 不互质的只有 \(p\) 的倍数）
若 \(\gcd(p,q)=1\) , 则 \(\varphi(pq)=\varphi(p)\times\varphi(q)\)
所有小于 \(n\) 与 \(n\) 互质的数的和 \(sum=n\timesφ(n)/2\)
证明：
如果 设\(\gcd(i,n)=1,\gcd(n-i,n)=k\)
则 \(n\equiv n-i\equiv i\equiv 0(\bmod\ k)\)
所以 \(k=1\)
所以比 \(n\) 小、与 \(n\) 互质的数成对出现。
计算欧拉函数：
设 \(n=p_1^{k_1}\times p_2^{k_2}\times ...\times p_n^{k_n}(p_i \in prime)\)
则
\(\varphi(n)=\varphi(p_1^{k_1})\times\varphi(p_2^{k_2})\times...\times \varphi(p_n^{k_n})\)
\(=(p_1^{k_1}-p_1^{k_1-1})\times (p_2^{k_2}-p_2^{k_2-1})\times...\times(p_n^{k_n}-p_n^{k_n-1})\)
\(=n\times \prod_{1}^{n}(1-1/p_i)\)
时间复杂度 \(O(\sqrt n)\)
int euler(int x)
{
int res=x;
for(int i=2;i<=x/i;i++){
if(x%i==0){
res=res*(i-1)/i;
}
while(x%i==0)x/=i;
}
if(x>1)res=res*(x-1)/x;
return res;
}
求 \([1,n]\) 所有数的欧拉函数：
复杂度 \(O(n \log n)\)
类似筛质数
void init()
{
ol[1]=1;
for(int i=2;i<=n;i++){
if(ol[i])continue;
for(int j=i;j<=n;j+=i){
if(!ol[j])ol[j]=j;
ol[j]=ol[j]*(i-1)/i;
}
}
}
欧拉定理
若 \(p\) 为任意自然数
\(a^{\varphi(p)}\equiv 1(\bmod\ p)\)
费马小定理为其特殊情况。