一、质数
1.质数的定义：
如果一个正整数无法被除了1和它本身以外的任何自然数整除，那么这个数是质数。否则，这个数是合数。
需要注意的是，1既不是质数也不是合数。
2.埃筛：
2.埃筛：
问题：给定一个正整数 \(n\) ，找到\(1\sim n\)中的所有质数。
思路：我们可以从 \(2\) 开始，从小到大扫描每个数。如果当前的数 \(x\) 是质数，就把它的不超过 \(n\) 的倍数\(2x,3x......\)全部标记为合数。最后所有未被标记的数就是质数。
时间复杂度\(O(n\space log\space log\space n)\)
for(int i=2;i<=n;++i)
if(!vis[i])
for(int j=i*2;j<=n;j+=i)
vis[j]=1;
3.欧拉筛：
在埃筛中，一个合数会被多次标记，如6会被2和3分别标记一次。
而欧拉筛运用“每个合数只会被它的最小质因数筛一次”的思想，将时间复杂度降低到了\(O(n)\)
思路：设一个数组\(v\)，\(v[i]\)表示 \(i\) 的最小质因数。将 \(2\sim n\) 扫描一遍。设当前的数是\(i\)：如果\(v[i]=0\)，说明 \(i\) 是质数，令 \(v[i]=i\) ，并统计到答案中。接下来扫描不大于 \(v[i]\) 的每个质数\(p\)，令\(v[i\times p]=p\)
for(int i=2;i<=n;++i){
if(v[i]==0)
v[i]=i,ans[++m]=i;
for(int j=1;j<=m;++j){
if(ans[j]>v[i]||ans[j]>n/i)
break;
v[i*ans[j]]=ans[j];
}
}
二、同余
1.定义：
如果整数 \(a\) 和整数 \(b\) 除以正整数 \(m\) 的余数相等，那么称 \(a,b\) 模 \(m\) 同余，记为：
\(a\equiv b (mod\space m)\)
2.同余的性质：
(1)反身性：\(a\equiv b(mod\space m) \iff b\equiv a(mod\space m)\)
(2)传递性：\(a\equiv b(mod\space m),b\equiv c(mod\space m) \longrightarrow a\equiv c(mod\space m)\)
(3)可加性：\(a\equiv b(mod\space m),c\equiv d(mod\space m) \longrightarrow a+c\equiv b+d(mod\space m)\)
(4)等幂性：\(a\equiv b(mod\space m) \iff a^n\equiv b^n(mod\space m)\)
(5)可约性：\(ac\equiv bc(mod\space m),gcd(c,m)=1 \iff a\equiv b(mod\space m)\)
3.欧几里得算法与扩展欧几里得算法：
欧几里得算法：
\(\forall a,b\in N,b\neq 0,\)有\(gcd(a,b)=gcd(b,a\%b)\)
证明：
若\(a<b\)，则 \(gcd(b,a\%b)=gcd(b,a)=gcd(a,b)\)
若\(a\leq b\)，不妨设 \(a=kb+r\) ，其中\(0\le r<b\)。显然\(r=a\%b\)。对于\(a,b\)的任意公约数\(d\)，\(\because d|a\)，\(d|kb\)，\(\therefore d|(a-kb)\)，\(d|r\)。因此\(d\)是\(b,r\)的公约数。
对于 \(b,r\) 的任意公约数 \(d\)，也能推出 \(d\) 是 \(a,b\) 的公约数。
因此 \(a,b\) 的公约数集合和 \(b,r\) 的公约数集合相同。所以它们的最大公约数相等。
证毕。
int gcd_(int a,int b){
if(b==0)
return a;
return gcd_(b,a%b);
}
扩展欧几里得算法：
前置知识：裴蜀定理：
\(\forall a,b\in N,\exists x,y\) 使得 \(ax+by=gcd(a,b)\)
证明：
在欧几里得定理的最后一步，即 \(b=0\) 时，显然有一对整数 \(x=1,y=0\)，使得\(a\times 1+0\times 0=gcd(a,0)=a\).
假设存在一对正整数 \(x,y\)，满足 \(bx+(a\%b)y=gcd(b,a\%b)\)。那么这时需要证明存在一对正整数\(x'\) , \(y'\) ,满\(ax'+by'=gcd(a,b)\).
我们把\(bx+(a\%b)y=gcd(b,a\%b)\)拆开，也就是\(bx+(a-b\lfloor\frac{a}{b}\rfloor)y=gcd(b,a\%b)\)
也就是\(ay+b(x-\lfloor\frac{a}{b}\rfloor y))=gcd(b,a\%b)\)。这时，只要令\(x'=y,y'=x-\lfloor\frac{a}{b}\rfloor y\)，就能得到\(ax'+by'=gcd(a,b)\).
证毕。
裴蜀定理的证明，实际上给出了整数\(x,y\)的计算方法。这种计算方法就是扩展欧几里得算法。
对于更为一般的方程\(ax+by=c\),它有解当且仅当\(gcd(a,b)|c\)。我们可以先求出\(ax+by=gcd(a,b)\)的一组解\(x_0,y_0\)，然后令\(x_0,y_0\)，同时乘以\(c/gcd(a,b)\)，就能求得\(ax+by=c\)的一组特解。
那么\(ax+by=c\)的通解就是：
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;
}
P1516 青蛙的约会
题目可以转化为 \(x+tm\equiv y+tn(mod\space l)\) ，令\(a=x-y\)，\(b=n-m\)，则 \(at\equiv b(mod\space l)\) 。然后就可以解线性同余方程了。注意负数的情况。
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;
}
signed main(){
scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
a=n-m;b=x-y;
if(a<0)
a=-a,b=-b;
if(b<0)
b=(b+l)%l;
if(b%__gcd(a,l)!=0){
printf("Impossible\n");
return 0;
}
exgcd(a,l,t,t1);
t=b/__gcd(a,l)*t;
t=(t%(l/__gcd(a,l))+(l/__gcd(a,l)))%(l/__gcd(a,l));
printf("%lld\n",(t%l+l)%l);
return 0;
}
4.逆元
如果\(ax\equiv 1(mod\space m)\),且 \(a\) 与 \(m\) 互质，那么 \(x\) 是 \(a\) 的模 \(m\) 乘法逆元
逆元的求法1：扩展欧几里得
我们只要将同余柿子转化成\(a\times x+m\times y=1\)，然后求解方程即可
逆元的求法2：费马小定理
费马小定理：若 \(m\) 是质数，且 \(a,m\) 互质,则 \(a^{m-1}\equiv 1(mod \space m).\)
所以\(a^{m-2}\times a\equiv 1(mod \space m).\) 所以我们要求的 \(x\) 就是\(a^{m-2}\)
注意：这种求法只适用于m是质数的情况。
逆元的求法3：线性算法
首先我们知道：\(1^{-1}≡1(mod\space p)\).
设\(p=ki+r,(1<r<i<p)\)，所以\(ki+r\equiv 0(mod\space p)\)
两边乘以\(i^{-1}r^{-1}\)可得：\(kr^{-1}+i^{-1}\equiv 0 (mod\space p)\)
\(i^{-1}\equiv -kr^{-1} (mod\space p)\)
\(i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor\times (p\space mod\space i)^{-1} (mod\space p)\)
int main(){
scanf("%d%lld",&n,&P);
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=(P-(P/i))*inv[P%i]%P;
for(int i=1;i<=n;++i)
printf("%lld\n",inv[i]);
return 0;
}
5.中国剩余定理和扩展中国剩余定理：
中国剩余定理：
设\(a_1,a_2,...,a_n\),是两两互质的整数，\(a=\Pi_{i=1}^na_i, A_i=a/a_i, t_i\) 是线性同余方程\(A_i t_i\equiv 1(mod\space a_i)\)的一个解。
则对于任意的 \(n\) 个整数\(b_1,b_2,...,b_n,\)方程组
有整数解，解为$x=\sum_{i=1}^n b_i A_i t_i $
证明：
原方程组可以拆解成为n个方程组：
即：
此时原方程组的解为：\(x=\sum_{i=1}^n x_i\)
令\(x_i=A_i k_i\)，则第 \(i\) 个方程组就转化为\(A_i k_i\equiv b_i, (mod\space a_i)\)
由题目可知，\(A_i t_i\equiv 1(mod\space a_i)\)，所以\(k_i=t_i b_i\)
所以\(x_i=A_i t_i b_i\)，所以整个方程组的解就是$x=\sum_{i=1}^nb_i A_i t_i $
证毕。
ll exgcd(ll &x,ll &y,ll a,ll b){
if(b==0){
x=1;y=0;return a;
}
ll re=exgcd(x,y,b,a%b);
ll tmp=x;x=y;y=tmp-a/b*y;
return re;
}
int main(){
scanf("%lld",&n);
s=1;
for(int i=1;i<=n;++i){
scanf("%lld%lld",&a[i],&b[i]);
s*=a[i];
}
for(int i=1;i<=n;++i){
exgcd(x,y,s/a[i],a[i]);
x=s/a[i]*((x+a[i])%a[i])*b[i];
ans=(ans+x)%s;
}
printf("%lld\n",ans);
return 0;
}
扩展中国剩余定理：
还是求解中国剩余定理的方程组，但不保证\(m_1,m_2,...,m_n\) 两两互质。
我们可以通过合并相邻方程的方式求解。
随便挑出两组方程： \(x\equiv a_i (mod\space m_i),x\equiv a_j (mod \space m_j)\)
我们把它转化为一般形式：\(x+y_i m_i=a_i,x+y_j m_j=a_m\)
也就是：\(a_i-a_j=y_i m_i-y_j m_j\)
其中，只有\(y_i,y_j\) 是未知数，所以可以看做关于\(y_i,y_j\)的二元一次方程。
根据裴蜀定理，如果\(a_i-a_j\)不能整除\(gcd(m_i,m_j)\)，那么方程无解。
假设一组特解是\(y_i=y_1,y_j=y_2\)，那么通解就是：
\(x\) 的特解是 \(x_0=a_i-y_1 m_i\)
\(x\) 的通解是
也就是 \(x=x_0-k\times lcm(m_i,m_j)\)
也就是\(x\equiv x_0 (mod\space lcm(m_i,m_j))\)
这样，我们就把两个方程合并成了一个方程。不断合并下去，就能求出原方程组的解。
ll mul(ll a,ll b,ll mod){
ll s=a;a=0;bool ok=0;
if(b<0)
b=-b,ok=1;
while(b){
if(b&1)
a=(a+s)%mod;
s=(s+s)%mod;b>>=1;
}
if(ok)
a=-a;
return a;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;y=0;return a;
}
ll re=exgcd(b,a%b,x,y);
ll tmp=x;x=y;y=tmp-y*(a/b);
return re;
}
ll excrt(){
ll y1=0,y2=0,x0=0,ans=0;
for(int i=2;i<=n;++i){
ans=exgcd(m[1],-m[i],y1,y2);
ll lcm=m[1]/__gcd(m[1],m[i])*m[i];
y1=mul(y1,m[1],lcm);
x0=(a[1]-mul(y1,(a[1]-a[i])/ans,lcm)+lcm)%lcm;
m[1]=lcm;a[1]=x0;
}
return x0;
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;++i)
scanf("%lld%lld",&m[i],&a[i]);
printf("%lld\n",excrt());
return 0;
}