数论

线性筛和欧拉函数

伟大的欧拉

Posted by JU on July 21, 2018

程序

#include <bits/stdc++.h>
#define sc(p) scanf("%d",&p)
const int N=10000100;
using namespace std;
int phi[N],prime[N]; bool vis[N];
void init (int gd)
{
    phi[1]=1;
    for (int i=2; i<=gd; i++)
    {
        if (!vis[i]) prime[++prime[0]]=i,phi[i]=i-1;
        for (int j=1; j<=prime[0]; j++)
        {
            long long k=prime[j]*i;
            if (k>gd) break;
            vis[k]=1;
            if (i%prime[j]==0)
            {
                phi[k]=phi[i]*prime[j];
                break;
            }
            else phi[k]=phi[i]*phi[prime[j]];
        }
    }
}
int main()
{
    int n; sc(n); init (n);
    return 0;
}

线性筛

一个O(n)筛质数的东东，思想是每个数都只用其最小的质因子去筛（程序已包含在上）。

欧拉函数

欧拉函数φ(n)（念phi）表示1~n中与n互质的数的个数。

（证明省略四万字）

性质

1.$φ(1)=1$
2.$当p为质，φ(p)=p-1$
3.$当gcd(a,b)=1,φ(ab)=φ(a)·φ(b)$（积性函数）
4.$当p为质，φ(p^{k})=(p-1)p^{k-1}$
（程序见上）

应用

欧拉定理

$若gcd(a,m)=1,a^{φ(m)}\equiv 1(mod \quad m)$
$当m为质，则a^{m-1}\equiv 1(mod \quad m)$，又称费马小定理

求逆元

一个数a模m意义下的逆元，记为$a^{-1}$，满足$a·a^{-1}\equiv 1(mod \quad m)$。
只有a与m互质情况下才有逆元。
由欧拉定理知$a^{φ(m)}\equiv 1(mod \quad m)$
故$a^{-1}=a^{φ(m)-1}$

降幂

当gcd(a,m)=1,$a^b\equiv a^{b\%φ(m)}(mod \quad m)$
否则$a^b\equiv a^{b\%φ(m)+φ(m)}(mod \quad m)$

推论

n以内与n互质的数是成对出现的，即若a<n，有$gcd(a,n)=1\Leftrightarrow gcd(n-a,n)=1$

滋磁

%%罗梓璋

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：线性筛和欧拉函数”
CATALOG
    FRIENDS