简单数论
wallace_QwQ · · 算法·理论
一.斐蜀定理
(1).内容：
若
(2).推广
1.逆定理
若
2.扩展
显然可以扩展到多个整数。
(3).进一步结论
对于
- 记
C=ab-a-b ，显然有C 为奇数。 - 可得
- 进而可得：对于方程
ax+by=c ，在[0,C] 中，恰有\frac{(a-1)(b-1)}{2} 个c 满足条件，即\forall n \in \mathbb{N},n,C-n 中有且只一个满足条件。二.丢番图方程
(1).形态：
a_1x_1^{b_1}+...+a_nx_n^{b_n}=c,a_{1...n},b_{1...n},c \in \mathbb{Z} (2).二元线性丢番图方程：
ax+by=c,a,b,c \in \mathbb{Z} 1.定理：
对于a,b,c\in\mathbb{Z},\exists x,y \in \mathbb{Z},使得ax+by=c\iff\gcd(a,b)\mid c 2.求解：
a.求出一个解：扩展欧几里得
先求解ax+by=\gcd(a,b) 不妨假设a>b,\gcd(a,b)=pa+qb 则有 \begin{aligned} ax+by &= \gcd(a,b)\\ &= \gcd(b,a \bmod b)\\ &= pb+q(a \bmod b)\\ &= qa+(p-q*\lfloor\frac{a}{b}\rfloor)b \end{aligned}
int extended_gcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int ret,xx=x,yy=y;
ret=extended_gcd(b,a%b,x,y);
x=yy,y=xx-a/b*yy;
return ret;
} b.所有解
若
特殊地，我们有最大正整数解和最小正整数解的关系为：
三.线性同余方程
(1).形态：ax \equiv c \pmod b
(2).求解：
int extended_gcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int ret,tmp;
ret=extended_gcd(b,a%b,x,y);
tmp=x,x=y,y=tmp-a/b*y;
return ret;
}
bool linear_equation(int a,int b,int c,int &x,int &y){
int d=extended_gcd(a,b,x,y);
if(c%d) return 0;
int k=c/d;
x*=k,y*=k;
return 1;
}四.第一类指数同余方程
(1).形式：a^x\equiv b\pmod p
(2).求解
令
则有：
即
预处理出
枚举
时间复杂度：
五.第二类指数同余方程
(1).形式：x^k\equiv b\pmod p
(2).求解：
设
假定
则
则
即
六.逆元
若
显然有
- 扩展欧几里得：
前提：
p 不一定是质数，a 为正整数，a \perp p 同解线性同余方程int extended_gcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } int ret,xx=x,yy=y; ret=extended_gcd(b,a%b,x,y); x=yy,y=xx-a/b*yy; return ret; } bool exgcd(int a,int b,int &x,int &y){ int d=extended_gcd(a,b,x,y); if(1%d) return 0; int k=1/d; x*=k,y*=k; return 1; } -
快速幂：
前提：
p 为质数，a 为正整数，a \perp p 根据费马小定理：若
p 为质数，a \perp p ，则a^{p-1} \equiv 1 \pmod p 则有
- 线性算法：
前提：
p 为质数，i 为正整数
显然有
1^{-1} \pmod p 不妨设
k 为p/i 的商，r为p/i 的余数\therefore k*i+r=p \therefore k*i+r \equiv 0 \pmod p 同乘
i^{-1}r^{-1} 可得：\therefore k*i^{-1}+i^{-1}\equiv 0 \pmod p \therefore i^{-1} \equiv -k*r^{-1} \pmod p \therefore i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor * (p \bmod i)^{-1} \pmod p
inv[1]=1;
for(int i=2;i<p;i++)
inv[i]=(p-p/i)*inv[p%i]%p;七.原根
模
若模
-
mod=1,2,4,p^{\alpha},2p^{\alpha}$，其中 $p$ 是奇素数，$\alpha\in\mathbb{N}_+ - 原根恰好有
\varphi(mod-1) 个 - 最小的原根一般不大，可以直接枚举
-
g$ 是原根当且仅当 $\forall d\mid(mod-1),d\ne mod-1\iff g^d\ne 1 八.二次剩余
勒让德符号：
\left(\dfrac{a}{p}\right)=\begin{cases}0&p\mid a\\1&\exists x^2\equiv a\pmod p\\-1&otherwise\end{cases}
欧拉准则：
二次互反律：对于奇素数
求解
前提：
随机一个
则
LL w,n,p;
struct num{
LL x,y;
num operator *(const num b){
num tmp;
tmp.x=((x*b.x%p+y*b.y%p*w%p)%p+p)%p;
tmp.y=((x*b.y%p+y*b.x%p)%p+p)%p;
return tmp;
}
};
LL qpow(num x,LL y,LL Mod=mod) {
if(y==0) return 1;
num res=x; y--;
for(;y;y>>=1,x=x*x)
if(y&1) res=res*x;
return res.x%Mod;
}
LL cipolla(LL n,LL p){
n%=p;
if(qpow(n,(p-1)/2,p)==p-1) return -1;
LL a;
while(1){
a=(rnd_64()>>1ll)%p;
w=(((a*a)%p-n)%p+p)%p;
if(qpow(w,(p-1)/2,p)==p-1) break;
}
num x={a,1};
return qpow(x,(p+1)/2,p);
}
void solve(){
cin>>n>>p;
if(!n){
cout<<"0\n";
return ;
}
LL ans1=cipolla(n,p),ans2=p-ans1;
if(ans1==-1) cout<<"Hola!\n";
else {
if(ans1==ans2) cout<<ans1<<"\n";
else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<"\n";
}
return ;
}九.中国剩余定理
(1).内容：
若自然数
- 计算
n_i 在\bmod m_i 意义下的逆元{n_i}^{-1} - 计算
c_i=n_i*{n_i}^{-1} (不对m_i 取模) - 则方程在
\bmod M 意义下的唯一解为：x=\sum_{i=1}^{r}a_ic_i \pmod M int extended_gcd(__int128 a,__int128 b,__int128 &x,__int128 &y){ if(!b){ x=1,y=0; return a; } __int128 ret,tmp; ret=extended_gcd(b,a%b,x,y); tmp=x,x=y,y=tmp-a/b*y; return ret; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>r; for1(i,1,r) cin>>m[i]>>a[i],M*=m[i]; for1(i,1,r){ n[i]=M/m[i]; extended_gcd(n[i],m[i],x,y); c[i]=n[i]*x; madd(ans,a[i]*c[i],M); } cout<<ans; return 0; }(3).扩展中国剩余定理：
若模数不两两互质。
先考虑
转化成不定方程
即
若
否则可以转化成
__int128 extended_gcd(__int128 a,__int128 b,__int128 &x,__int128 &y){
if(!b){
x=1,y=0;
return a;
}
__int128 ret,tmp;
ret=extended_gcd(b,a%b,x,y);
tmp=x,x=y,y=tmp-a/b*y;
return ret;
}
bool linear_equation(__int128 a,__int128 b,__int128 c,__int128 &x,__int128 &y){
__int128 d=extended_gcd(a,b,x,y);
if(c%d) return 0;
__int128 k=c/d;
x*=k,y*=k;
return 1;
}
void solve(){
cin>>r;
for1(i,1,r) {
rin(m); rin(a);
linear_equation(M,-m,a-A,p,q);
A=M*p+A,M=lcm(M,m);
madd(A,M,M);
}
rout(A);
return ;
}(4).大部翻倍法
void merge(LL &a1,LL &m1,LL a2,LL m2){
if(m1<m2) swap(m1,m2),swap(a1,a2);
while(a1%m2!=a2) a1+=m1;
m1=lcm(m1,m2);
}
void solve(){
cin>>n;
v=0,d=1;
for1(i,1,n){
cin>>a>>m;
a%=m;
merge(v,d,a,m);
}
cout<<v<<"\n";
}十.积性函数
(1).定义
积性函数：对于函数
完全积性函数：对于函数
- 常见的积性函数：
\varphi,\mu,\sigma,d - 常见的完全积性函数：
\varepsilon,I,id
其中：
积性函数的性质：
- 设
n=\prod p_i^{\alpha_i} ，那么f(n)=\prod f(p_i^{\alpha_i}) - 于是可以用线性筛求出
g(n)=p_1^{\alpha_1} ，然后f(n)=f(g(n))f(\frac{n}{g(n)}) ，在O(n) 时间内预处理积性函数的值。
- 于是可以用线性筛求出
- 若
f(n) ，g(n) 都是积性函数，那么fg ，f/g 都是积性函数。(2).欧拉函数
\varphi 1.定义
若
n=\prod_{i=1}^{s}{p_i}^{k_i} ，其中p_i 为质数，则\varphi(n)=n\prod_{i=1}^{s}\frac{p_i-1}{p_i} ，表示小于等于n 和n 互质的数的个数$2.性质：
-
若n为质数，\varphi(n)=n-1 -
若n为奇数，\varphi(n)=\varphi(2n) -
若a \perp b,\varphi(ab)=\varphi(a)\varphi(b) -
n=\sum_{d \mid n}\varphi(d) -
若n=p^k,且p为质数，\varphi(n)=p^k-p^{k-1} 3.求法
a.单个：
int euler_phi(int n){ int ans=n,sq=sqrt(n); for1(i,2,sq) if(n%i==0){ ans=ans/i*(i-1); while(n%i==0) n/=i; } if(n>1) ans=ans/n*(n-1); return ans; }b.多个：
筛法： 设p_1为n的最小质因子，n'=\frac{n}{p_1}，显然有\varphi(p_1)=p_1-1 若n'\bmod p_1=0,\varphi(n)=p_1*\varphi(n') 若n'\bmod p_1\ne0,\varphi(n)=\varphi(p_1)*\varphi(n') void euler_phi(int n){ phi[1]=1; for1(i,2,n){ if(!vis[i]) pri.p_b(i),phi[i]=i-1; for(int j: pri){ if(i>n/j) break; vis[i*j]=1; if(i%j==0){ phi[i*j]=phi[i]*j; break; } phi[i*j]=phi[i]*phi[j]; } } }(3).莫比乌斯函数
\mu 1.定义
\mu(n)= \begin{cases} 1&n=1\\ 0&n的质因子最高次数>1\\ (-1)^k&n的质因子最高次数=1 \end{cases} 其中
k 为n 的质因子个数。2.性质
\begin{cases} 1&n=1\\ 0&n\ne1 \end{cases}
-
即
3.求法
线性筛：
void get_mu(int n){
mu[1]=1;
for1(i,2,n){
if(!vis[i]) pri.p_b(i),mu[i]=-1;
for(int j: pri){
if(i>n/j) break;
vis[i*j]=1;
if(i%j==0){
mu[i*j]=0;
break;
}
mu[i*j]=-mu[i];
}
}
}(4).约数之和 \sigma 与 约数个数 d
1.定义
若
则：
$=\prod\limits_{i=1}^n(\sum_{j=0}^{\alpha_i}p_i^j)$
$=\prod\limits_{i=1}^n\frac{1-p_i^{\alpha_i+1}}{1-p_i}$2.求法
- 线性筛求
d ```cpp void make_d(){ t[1]=d[1]=1; for1(i,2,n){ if(!vis[i]) pri.p_b(i),t[i]=1,d[i]=2; for(int j: pri){ if(i>n/j) break; vis[i*j]=1; if(i%j==0){ t[i*j]=t[i]+1; d[i*j]=d[i]*(t[i*j]+1)/(t[i]+1); break; } t[i*j]=1; d[i*j]=d[i]*d[j]; } } } ``` - 线性筛求
\sigma ```cpp void make_sgm(){ sigma[1]=1; for1(i,2,n){ if(!vis[i]) pri.p_b(i),t[i]=i+1,sigma[i]=i+1; for(int j: pri){ if(i>n/j) break; vis[i*j]=1; if(i%j==0){ t[i*j]=t[i]*j+1; sigma[i*j]=sigma[i]*t[i*j]/t[i]; break; } t[i*j]=j+1; sigma[i*j]=sigma[i]*sigma[j]; } } } ``` ****** # 十一.欧拉定理 ## (1).内容： 若 $\gcd(a,m)=1$，则 $a^{\varphi(m)} \equiv 1\pmod m (2).扩展：
a^b\equiv \begin{cases} a^{b\bmod\varphi(m)},& \gcd(a,m)=1\\ a^b,& \gcd(a,m)\ne 1,b<\varphi(m)\\ a^{(b\bmod\varphi(m))+\varphi(m)}&\gcd(a,m)\ne 1,b\ge\varphi(m) \end{cases} \pmod m 十二.威尔逊定理
对于素数
p 有(p-1)!\equiv-1\pmod p 十三.数论分块
一般用来求形如
\sum_{i=1}^nf(i)g(\lfloor\frac{n}{i}\rfloor)
若可以
我们考虑将
UVA11526 H(n)
LL H(LL n){
LL ans=0;
for(LL i=1,j;i<=n;i=j+1){
j=n/(n/i);
ans+=(j-i+1)*(n/i);
}
return ans;
}