欧拉函数与逆元
定义:一个正整数内(包含自身)所有与自身互质的数的个数.1与所有数互质,即phi[1]=1
几个式子1.n为任意数,phi[n]=n*(1-1/n1)(1-1/n2)…(1-1/nn) n1到nn是n的质因子
2.如果n是一个质数 phi[n]=n-1;
3.如果n是一个奇数 phi[2n]=phi[n] (根据式子1得到)
4.如果gcd(n,m)=1,即是n与m互质,那么它们的质因子没有交集,根据1式子得到phi[nm]=phi[n]phi[m]
5.如果n的质因子集是m的质因子集的子集,那么phi[nm]=n*phi[m]
typedef long long ll;
const ll N=1e7+10;
ll phi[N],prime[N];
void Euler_sieve(ll n)
{
ll t=0;
for(ll i=2;i<=n;i++){
if(phi[i]==0)
phi[i]=i-1,prime[t++]=i; //式子2
for(ll j=0;j<t&&prime[j]*i<=n;j++){
// 保证线性的
if(i%prime[j]==0){
// 式子5
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
// 式4
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
代码.求解单个phi[i]
using ll=long long;
ll Euler(ll n)
{
ll ans=n;
for(ll i=2;i*i1) ans-=ans/n;
return ans;
}
欧拉定理
设a,p互质,则有
aphi[p]恒等于1%p
设集合A为phi[p]里面所有与p互质的小于等于p的元素
那么设集合B为集合A中每个元素与a相乘的集合
可以证明B中集合的元素模上p的值是唯一的(任意两个元素相减得a(Ai-Aj),a与p互质,A中元素都小于等于p,相减后一定小于p,所以没有使任意两数相减模上p为0的两个数,所以唯一)
因为所有小于等于且与p互质的元素都在A中,那么集合B%p等于集合A
得 aphi[p]恒等于1%p
定义:如果两个数a,b,它们的乘积模上p等于1,那么它们互为关于模数p的数论倒数
(a+b)%p=(a%p+b%p)%p
(a-b)%p=(a%p-b%p)%p 需要判断a与b的大小,如果a>b,结果要保证为正,即最后结果+p再%p,…
(a*p)%p=(a%p * b%p)%p
没有除法的
因为ap-2恒等于1/a%p (p是质数)
所以可以转换成ap-2%p
ll inv1(ll a,ll mod)
{
ll p=mod;
mod-=2;
ll ans=1;
while(mod)
{
if(mod&1)
ans=(ans*a)%p;
a=(a*a)%p;
mod>>=1;
}
return ans%p;
}
通过欧拉值(phi[p])求解(a与p互质)
aphi[p] 恒等于 1%p 得出 aphi[p]-1 恒等于 1/a%p
ll phi(ll n){
ll ans=n;
for(ll i=2;i*i1) ans-=ans/n;
return ans;
}
ll inv2(ll m,ll n){
ll b=phi(n)-1,ans=1;
while(b){
if(b&1) ans=(ans*m)%n;
m=(m*m)%n;
b>>=1;
}
return ans;
}
扩展欧几里得
扩展欧几里得存在ax+by=gcd(a,b)
如果模数是b,被摸数是a,那么上式转换为a*x%b=gcd(a,b)%b,x/gcd(a,b)%b=1/a%b
所以可以转换为x/gcd(a,b)%b 因为gcd(a,b)==1(b是质数).所以就是x%b=1/a%b
如果x是个负值,需要加上一个p
ll x,y,g;
int in3(ll a,ll b)
{
if(!b)
{
x=1,y=0,g=a;
return x/g;
}
inv2(b,a%b);
ll c=x;
x=y,y=c-(a/b)*y;
return x/g;
}
递推
设被摸数为a,模数为p,则x=p/a,y=p%a
(x*a+y)%p=0%p
y%p=(p-x)*a%p 移动时,保证两边的正负性一样
1/a%p=((p-x)*1/y)%p
1/a%p=(p-p/a)*1/(p%a))%p
求解1/a关于p的逆元, 就要求解1/(p%a)关于p的逆元
一直递归下去,直到为1,因为1的逆元就是1
void inv4(ll a,ll mod,ll num[])
{
for(ll i=2; i<=a; i++)
num[i]=((mod-mod/i)*num[mod%i])%mod; //num存的是逆元
}
作者：hire_candidate
