前知导入
唯一分解定理
对于任何一个大于 \(1\) 的正整数都能分成有限个质数的乘积
即若 \(n\) 为大于 \(1\) 的整数，则有：\(n=\prod \limits_{i=1}^{m}p_i^{c_i}\)
其中，\(p_i\) 为质数且递增，\(p_i\leq n,c_i\geq 0\)
容斥原理
在此仅做简单引入
带入情景，班里有 \(10\) 个同学喜欢数学，\(5\) 个喜欢语文，\(8\) 个喜欢英语，求至少喜欢一门的学生个数
这个问题很好解决，讲喜欢这三科的学生的集合分别记作 \(A,B,C\)，则至少喜欢一门的学生表示为 \(|A\cup B\cup C|\)
则 \(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B \cap C|+|A\cap B\cap C|\)
这就是简单的容斥原理
定义
写作 \(\varphi(n)\)，表示小于等于 \(n\) 的正整数中与 \(n\) 互质的个数
求\(\varphi(n)\)
通式
\[\varphi(n)=\begin{cases} 1&n=1\\ n\times \prod\limits_{p\in\mathbb{p},p|n}(1-\dfrac{1}{p})&i\neq 1\\ \end{cases}\]证明：
当 \(n>1\) 时，根据唯一分解定理，设 \(n=\prod\limits_{i=1}^{m}p_i^{c_i}\)其中 \(p_i,p_j\) 为 \(n\) 的质因子
则 \(1\sim n\) 中，\(p_i\) 的倍数有 \(\dfrac{n}{p_i}\) 个，\(p_j\) 的倍数有 \(\dfrac{n}{p_j}\) 个
根据容斥原理，\(1\sim n\) 中不与 \(n\) 有共同因子 \(p_i\) 或 \(p_j\) 的个数为 $$n-\dfrac{n}{p_i}-\dfrac{n}{p_j}+\dfrac{n}{p_i\times p_j}=n\times (1-\dfrac{1}{p_i}-\dfrac{1}{p_j}+\dfrac{1}{p_i\times p_j})=n\times (1-\dfrac{1}{p_i})\times (1-\dfrac{1}{p_j})$$
以此类推，将 \(n\) 的全部质因子全部代入容斥原理，即可得到 \(\varphi(n)\)
代码实现
1. 线性筛法求 \(1\sim n\) 的欧拉函数
时间复杂度 \(O(n)\)
void euler(int n)
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i])
len++,
prime[len]=i,
phi[i]=i-1;
for(int j=1;j<=len&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
2. 求单个数的欧拉函数
先对其分解质因数，然后带入公式
单个数的复杂度为 \(O(\sqrt n)\)
int phi(int x)
{
int ret=x;
for(int i=2;i<=sqrt(n);i++)
if(x%i==0)
{
ret=ret/i*(i-1);
while(x%i==0) x/=i;
}
if(x>1) ret=ret/x*(x-1);
return ret;
}
性质
1. 当 \(n\) 为质数时，\(\varphi(n)=n-1\)
- 显然
2. 欧拉函数是积性函数
当 \(\gcd(a,b)=1\) 时，\(\varphi(a\times b)=\varphi(a)\times \varphi(b)\)
由此不难推出，当 \(n\) 为奇数时，\(\varphi(2n)=\varphi(n)\)
-
证明：
根据唯一分解定理，不妨设 \(a=\prod\limits_{i=1}^{m}p_i^{c_i},b=\prod\limits_{i=1}^{m}q_i^{d_i}\)
因为 \(\gcd(a,b)=1\)，所以一定不存在一组 \(p_i=q_j\)
那么 \(ab\) 可分解为 \(\prod\limits_{i=1}^{m}p_i^{c_i}\times \prod\limits_{i=1}^{m}q_i^{d_i}\)，其中 \(p,q\) 一定不相等
故此，依据性质 \(2\)，则有 \(\varphi(ab)=ab\times \prod\limits_{i=1}^n(1-\dfrac{1}{p_i})\times \prod\limits_{i=1}^m(1-\dfrac{1}{q_i})\)
又因为 \(\varphi(a)=a\times \prod\limits_{i=1}^n(1-\dfrac{1}{p_i}),\varphi(b)=b\times \prod\limits_{i=1}^m(1-\dfrac{1}{q_i})\)
所以得到 \(\varphi(ab)=\varphi(a)\times \varphi(b)\)
3. 欧拉反演
\[n=\sum\limits_{d|n}\varphi(d)=\sum\limits_{d|n}\varphi(\dfrac{n}{d}) \]- 根据约数 \(d,\dfrac{n}{d}\) 的对称性
4. 若 \(n=p_k\) 且 \(k\) 为质数，那么 \(\varphi(n)=p_k-p_{k-1}\)
- 根据定义可得
5. 若 \(m|n\) 则 \(\varphi(n)=\dfrac{n}{m}\varphi(m)\)
- 由欧拉函数是积性函数可得
相关知识扩展
欧拉定理
若正整数 \(a,b\) 满足 \(\gcd(a,b)=1\) ，则 $$a^{\varphi(m)}\equiv 1(\bmod m)$$
- 在此只做描述，
暂时未学费马小定理，不会证
扩展欧拉定理
\[a_b=\begin{cases} a^{b\bmod \varphi(p)}&\gcd(a,p)=1\\ a^b&\gcd(a,p)\neq 1,b<\varphi(p)~~~~~~~~~(\bmod p)\\ a^{b\bmod \varphi(p)+\varphi(p)}&\gcd(a,p)\neq 1,b\geq\varphi(p)\\ \end{cases}\]例题
1. 仪仗队
题目链接 \(仪仗队\)
问题处理
如图：
这是一个正方形，不放将他看做一个三角形，再乘以 \(2\)
以左下角点为原点 \((0,0)\) 建立坐标系
设一点 \((x,y)\)，当 \(x,y\) 互质时，即 \(\gcd(x,y)=1\) 时，他可以被看到
反之，则一定有一点 \((\dfrac{x}{\gcd(x,y)},\dfrac{y}{gcd(x,y)})\) 将他挡住
问题可转化为：\(i=1\sim (n-1)\) 中分别与 \(0\sim (i-1)\) 互质的个数
也就是求 \(2\times \sum\limits_{i=1}^{n-1}\varphi(i)+1\)
因为欧拉函数求的是 \(1\sim (i-1)\) 中与 \(i\) 互质的个数，但这里是从 \(0\) 开始的，所以纵坐标是 \(0\) 的这一条线上 \((1,0)\) 是可以看到的，后面都挡住了，所以要 \(+1\)； \(\times 2\) 显然，因为我们是将他看做一个三角形去做的
注意事项： 是 \(1\sim (n-1)\) 而不是 \(1\sim n\)，因为我们的第一列在坐标轴中视作 \(y=0\) 了
代码如下
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=4e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n,len,ans,phi[N],prime[N],vis[N];
void euler(int n)
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i])
len++,
prime[len]=i,
phi[i]=i-1;
for(int j=1;j<=len&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n);
euler(n);
for(int i=1;i<n;i++) ans+=phi[i];
cout<<(ans<<1)+1;
}
这里采用筛法求 \(1\sim (n-1)\) 的欧拉函数，复杂度 \(O(n)\)，因为要求 \(1\sim (n-1)\) 的欧拉函数的和
2. \(Longge\) 的问题
题目链接 \(Longge的问题\)
问题处理
求 \(\sum\limits_{i=1}^{n}\gcd(i,n)\)
依据 \(\gcd\) 为积性函数
\[\begin{align} &\sum\limits_{i=1}^{n}\gcd(i,n)\\ &=\sum\limits_{d|n}d\sum\limits_{i=1}^{d}[\gcd(i,n)=d]\\ &=\sum\limits_{d|n}d\sum\limits_{i=1}^{\dfrac{n}{d}}[\gcd(i,\dfrac{n}{d})=1]\\ &=\sum\limits_{d|n}d\times\varphi(\dfrac{n}{d})=\sum\limits_{d|n}\dfrac{n}{d}\times\varphi(d)（依据d与\dfrac{n}{d}的对称性）\\ \end{align}\]由此求即可
代码如下
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n,len,ans;
int phi(int x)
{
int ret=x;
for(int i=2;i<=sqrt(n);i++)
if(x%i==0)
{
ret=ret/i*(i-1);
while(x%i==0) x/=i;
}
if(x>1) ret=ret/x*(x-1);
return ret;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n);
for(int i=1;i<=sqrt(n);i++)
if(n%i==0)
if(i*i!=n) ans+=i*phi(n/i),ans+=(n/i)*phi(i);
else ans+=i*phi(i);
cout<<ans;
}
根据 \(d,\dfrac{n}{d}\) 的对称性，只需要 \(O(\sqrt n)\) 即可
3. 沙拉公主的困惑
题目链接 \(沙拉公主的困惑\)
问题处理
简化题意：求 \(\sum\limits_{i=1}^{n!}[\gcd(i,m!)=1]\)
\[\begin{align} &\sum_{i=1}^{n!}[\gcd(i,m!)=1]\\ &=\dfrac{n!}{m!}\varphi(m!)\\ &=\dfrac{n!}{m!}\times m!\times \prod_{{p\in{p},p|m!}}(\dfrac{p-1}{p})\\ &=n!\times \prod_{{p\in\mathbb{p},p|m!}}(\dfrac{p-1}{p})\\ &=n!\times \prod_{p\in\mathbb{p}}^{m}(\dfrac{p-1}{p})\\ \end{align}\]由此求即可
程序实现
多组测试数据，所以要先预处理（递推||筛法），不然显然会超时
先设一个 \(N\) ，即数据范围，输入中给了总的 \(\bmod P\)
根据上面推出的式子，需要先处理 质数，阶乘，乘法逆元，\(\prod\limits_{i\in\mathbb{p}}^{N}(\dfrac{i-1}{i})\)
- 质数是为了处理 \(\prod\limits_{i\in\mathbb{p}}^{N}(\dfrac{i-1}{i})\) 的
- 阶乘显然是为了处理 \(n!\)的，别忘了 \(\bmod P\)
- 至于乘法逆元，因为在 \(\bmod P\) 意义下，直接除以 \(i\) 是不行的，要用到 \(i^{-1}(\bmod P)\)
- 之后就可以处理 \(\prod\limits_{i\in\mathbb{p}}^{N}(\dfrac{i-1}{i})\)
这样对于每一组输入，直接 \(O(1)\) 输出即可
代码如下
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e7+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int t,p,n,m,jc[N],ans[N],inv[N];
bool pri[N];
void niyuan()
{
inv[1]=1;
for(int i=2;i<N;i++)inv[i]=((p-p/i)*inv[p%i])%p;
}
void prime()
{
for(int i=2;i<sqrt(N);i++)
if(!pri[i])
for(int j=2;i*j<N;j++)
pri[i*j]=1;
}
void prod()
{
jc[1]=1;
for(int i=2;i<N;i++) jc[i]=(jc[i-1]*i)%p;
}
void solve()
{
ans[1]=1;
for(int i=2;i<N;i++)
if(!pri[i]) ans[i]=(ans[i-1]*(i-1))%p,ans[i]=(ans[i]*inv[i])%p;
else ans[i]=ans[i-1];
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(t),read(p);
niyuan(),prime(),prod(),solve();
while(t--)
read(n),read(m),
cout<<(jc[n]*ans[m])%p<<endl;
}
此处注意数组开的是 \([N]\)，预处理的时候不能处理到 \(N\) 而应是 \(N-1\)，不然会炸数组
标签：函数,limits,dfrac,varphi,times,prod,欧拉,gcd From： https://www.cnblogs.com/Charlieljk/p/17941329