\({\color{Red} 声明：由于作者是个蒟蒻，所以本博客只含结论，不含推导过程。如果有大佬想看推导过程可以看 (这里是传送门)}\) oi-wiki,教练，HaneDaniko
素数
筛法求素数
- 用于求1~n的素数
线性筛
点击查看代码
int prime[maxn]; // 保存素数
bool is_not_prime[maxn]={1,1}; // 0和1都不是素数
// 筛选 n 以内的所有素数
void xxs(int n)
{
for(int i=2;i<=n;++i) {
if(!is_not_prime[i]) // 如果i是素数
{
prime[++prime[0]]=i;
}
for(int j=1;j<=prime[0]&&i*prime[j]<=n;++j)
{
is_not_prime[i*prime[j]] = 1;
// 如果i中包含了该质因子，则停止
if(i%prime[j]==0)break;
}
}
}
埃氏筛
点击查看代码
int n,a[50000005];
int main()
{
scanf("%d", &n);
for(int i=1;i<=n;i++)a[i]=1;
for(int i=2;i<=n;i++)
{
if(a[i] == 0)continue;
for(int j=i;j<=n/i;j++)
{
a[i*j] = 0;
}
}
for(int i=2;i<=n;i++)
{
if(a[i])printf("%d\n",i);
}
return 0;
}
欧拉函数
- 用于求i:1~n中与n互质的数(
gcd(i,n)==1)的个数，用\(\varphi\)表示。 - 特殊性质：
- \(\varphi(1)=1\)
- p是一个素数\(\varphi(p)=p-1\),\(\varphi(p^k)=(p-1)\times p^{k-1}\)
- 若\(gcd(a,b)=1\)，则\(\varphi(a\times b)=\varphi(a)\times \varphi(b)\),特殊的:对于奇数n\(\varphi(2n)=\varphi(n)\)
求欧拉函数
- 只求一个数的欧拉函数
点击查看代码
```cpp int euler_phi(int n) { int m=int(sqrt(n+0.5)); int ans=n; for(int i=2;i<=m;i++) { 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; } ```- 求1~n所有数的欧拉函数
点击查看代码
int n,phi[N],prime[N],tot;
bool not_prime[N];
void getPhi()
{
int i,j,k;
phi[1]=1;
for(i=2;i<=n;++i)
{
if(!not_prime[i])
{
prime[++tot]=i;
phi[i]=i-1;
}
for(j=1;j<=tot;++j)
{
k=i*prime[j];
if(k>n)break;
not_prime[k]=true;
if(i%prime[j]==0)
{
phi[k]=prime[j]*phi[i];
break;
}
else phi[k]=(prime[j]-1)*phi[i];
}
}
}
费马小定理
- 模数为素数
- 若p是素数，a不是p的倍数(或\(gcd(a,p)=1\))，则\(a^{p-1} \equiv 1 \pmod p\)。
- 另一种形式：若p为素数，对任意整数a，有\(a^p\equiv a \pmod p\)。
欧拉定理
- 费马小定理是用来阐述在素数模下，指数的同余性质。当模是合数时，就要用范围更广的欧拉定理了。
- 若\(gcd(a,m)=1\)，则\(a^{\varphi(m)}\equiv 1 \pmod m\)。
- 特别的：当m为素数时，就是费马小定理。
拓展欧拉定理
\[a^b= \begin{cases} a^{b\,mod\,\varphi(p)} \qquad\qquad gcd(a,p)=1\\ a^b \qquad\qquad\qquad\,\;\;\; gcd(a,p)\neq1 ,b<\varphi(p)\pmod m\\ a^{b\,mod\,\varphi(p)+\varphi(p)} \qquad gcd(a,p)\neq1 ,b\ge\varphi(p) \end{cases} \]最大公约数
- 新版本的dev中有直接求最大公约数的函数
__gcd(a,b)(这是两个下划线)，据说比赛里也可以用。
辗转相除法求最大公约数
- 原理：\(gcd(x,y)=gcd(y,x\;mod\;y)\)
点击查看代码
//递归形式
int gcd(int x,int y)
{
return(y==0?x:gcd(y,x%y));
}
//非递归形式
int gcd(int x,int y)
{
int r=x%y;
while(r)
{
x=y;
y=r;
r=x%y;
}
return y;
}
裴蜀定理
- a，b为两个不全为零的整数，对任意整数x，y，满足\(gcd(a,b)\,|\,ax+by\),
则存在整数x，y使\(ax+by=gcd(a,b)\)。 - 逆定理：a，b是不全为零的整数，若\(d(d>0)\)是a，b的公因数，且存在整数x，y，使得\(ax+by=d\),则\(d=gcd(a,b)\)。
- 特殊的，a，b为不全为零的整数，若存在整数x，y，使得\(ax+by=1\)，则a，b互质。
拓展欧几里得
- 常用于求\(ax+by=gcd(a,b)\)的一组整数解（x，y为未知数）。
求任意一组解
点击查看代码
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x = 1;
y = 0;
return a;
}
int ret=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return ret;
}
- 这个函数的返回值既不是x也是不y，而是a，b的最大公约数，这也是函数传参数时要带&的原因（这样可以改变原参数值）。
求最小正整数解和同解
- 若\((x_0,y_0)\)，为任意一组解，则同解\((x,y)\)为
其中t为任意整数
标签：prime,phi,gcd,推导,int,varphi,板子,素数,数学 From： https://www.cnblogs.com/wang-qa/p/18093984