题解 P5091
hanzhongtlx
·
·
题解
更好的阅读体验点这里
这篇文章的动机：万一有什么长进呢？（先痴想一下吧）
本文难度：\color{orange}\text{普及-}→\color{CornflowerBlue}\text{提高+}
Part\;1.线性筛
不止能筛质数，所有的积性函数都可以O(n)筛出。
当然不排除你喜爱埃氏筛，但洛谷$1e8$照样会卡你。
但不能略过：
埃氏筛，全称是啥显然忘了（用不到吧$qwq$?）,核心思想是利用已有的质数，与当前的数相乘，得到的一定是合数。
下面是线性筛质数：
```
judge[1]=true;
for(int i=2;i<=maxn;i++)
{
if(i*i>maxn) continue;
if(!judge[i])
{
for(int j=2*i;j<=maxn;j+=i) judge[j]=true;//是合数
}
}
```
一看就懂吧。
复杂度分析（~~并不会~~）：
我们知道素数密度是$\dfrac{n}{\ln n}$的，那么对于每个合数$x$要筛$\dfrac{maxn}{x}$次然而他求和是接近$\log n$的（难死了），所以应该是$O(n\log\log n)$，近似于常数了（这改变不了他被卡的命运）
那大神欧拉发现（这谁都可以），有些数会被筛好几次，这就是他不能$O(n)$的原因,比如$6$，被$2,3$筛两次，那我们可以这样写：
```
for(int i=2;i<=maxn;i++)
{
if(!judge[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&(prime[j]*i)<=maxn;j++)
{
judge[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
```
为什么只会筛一次呢？
考虑如果整除，那就有一个平方因子也可以筛掉他，丢到后面去就好了。
所以复杂度就是$O(n)$的，再卡就没办法了。
## $Part\;2$.欧拉函数
定义欧拉函数$\psi(n)$为与$n$互质的数，一个大佬讲得贼好：
$\psi(6)$咋算？这里是可以枚举的，是$O(n\log n)$，他讲了种好方法：
写出所有分母是$6$的不大于$1$的分数。
$$\dfrac{1}{6},\dfrac{2}{6},\dfrac{3}{6},\dfrac{4}{6},\dfrac{5}{6},\dfrac{6}{6}$$
化简后分组：
$$\dfrac{1}{6},\dfrac{1}{3},\dfrac{1}{2},\dfrac{2}{3},\dfrac{5}{6},\dfrac{1}{1}$$
那么：
$$\psi(6)=2,\psi(3)=2,\psi(2)=1,\psi(1)=1$$
然后就说明:
$$\sum_{d|n} \psi(d)=n$$
显然观察归纳不严密，若我有幸学习并会了了莫反再来证吧。
## $Part\;3$.线性求法
欧拉函数是积性函数，保证了它可以被$O(n)$筛出，但原理较复杂，建议先别学$qwq$，看完下面就好多了，~~反正我是~~。
## $Part\;4$.单个数的欧拉函数
考虑一个事:
$$\text{若}x\in P,\psi(x)=x-1$$
只有自身不互质,我们称为性质一。
性质二：考虑一个**合数**$a$满足$a=p^k(k>1,k\in Z)$,显然与他互质的数$b\in [p,2p,3p......p^{k-1}p]$(饶了我吧，我真不会打大括号)。
那么$\psi(a)=p^k-p^{k-1}=p^k(1-\dfrac{1}{p})$。
性质三：最一般的情况，每个合数$a$都可写成唯一分解式：
$$a=p_1^{k_1}p_2^{k_2}......p_n^{k_n}$$
即：
$$a=\prod_{i=1}^n p_i^{k_i}$$
好在欧拉函数是个特殊的积性函数，满足$\psi(nm)=\psi(n)\psi(m)$，成立（当然在定义域)。
那么
$$\psi(a)=\prod_{i=1}^n \psi(p_i^{k_i})=\prod_{i=1}^n p_i^{k_i}\prod_{i=1}^n(1-\dfrac{1}{p_i})=a\prod_{i=1}^n(1-\dfrac{1}{p_i})$$
到这里，我们就可以$O(\sqrt{n})$得出 一个数的欧拉函数了。 其实思想和早先我们学习质数验证枚举因子是异曲同工的：
代码：
```
int phi(int n)
{
int ans=n;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);//这是一个p，注意先除再乘，防止炸int
while(n%i==0) n/=i; //把质数次方因子筛没了，就不会错了
}
}
if(n>=2) ans=ans/n*(n-1);//最后有可能剩下
return ans;
}
```
不过有些人不这样写：
```
int phi(int n)
{
int ans=1,now;
for(int i=1;i<=sqrt(n);i++)
{
now=1;
if(n%i==0)
{
now=i-1,n/=i;
while(n%i==0) now*=i,n/=i;
}
ans*=now;
}
if(n!=1) ans*=n-1;
return ans;
```
简单说下，对于一小部分($p^k$)考虑变形：
$$\psi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$$
于是发现出现质数$p$先乘一次$p-1$,再来$k-1$次$p$，其他都是一样的，不过这里：
```
now=i-1,n/=i;
```
注意除一下，然后$now,ans$分别记录，不能够混淆。
## $Part\;5$.回归$Part\;3
剩下的就好说了。
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]) p[++cnt]=i,phi[i]=i-1;//质数只有自身与自己不互质
for(int j=1;p[j]&&i*p[j]<=n;j++)
{
vis[i*p[j]]=1;
if(!(i%p[j]))
{
phi[i*p[j]]=phi[i]*p[j];
//这里是平方因子了，不要减1
break;
}
else phi[i*p[j]]=phi[i]*(p[j]-1);//第一次出现因子，乘p-1
}
}
精华都在代码里了。
其实和筛素数的是一样的。
线性筛可是很NB的，以至于所有积性函数都怕他（掩盖不了看似大的惊人的复杂度了）。
Part\;6 欧拉定理
前置知识：快速幂。
大概这样写,复杂度是O(\log n)的。
ll quickpow(ll a,ll b)
{
ll ans=1,base=a;
while(b!=0)
{
if(b&1!=0)//b%2==1;
{
ans*=base;
}
base*=base;
b>>=1;//b/=2;
}
return ans;
}
你甚至可以自己定义乘法运算跑快速幂。
可是指数很大怎么办呢？
连O(\log n)都过不去啊！
伟大的欧拉提出了定理，我们为了纪念他，称为欧拉定理：
若\gcd (a,m)=1,则：
a^{\psi(m)}\equiv1\pmod{m}
但他认为不够，又提出了拓展欧拉定理：
a^b\equiv\begin{cases}a^b&b<\psi(m)\\a^{b\;mod\;\psi(m) +\psi(m)}&b\geqslant \psi(m)\end{cases}
这样，先预处理出\psi(m)，再用字符串边读边模即可。
复杂度大概是O(len_b+\sqrt{m}+\log m)(毕竟\psi(m)上界是m),可以通过本题。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int phi(int x)//欧拉函数
{
int ans=1,num=1;
for(int i=2;i*i<=x;i++)
{
if(!(x%i))
{
num=i-1,x/=i;
while(!(x%i)) num=num*i,x/=i;
ans=num*ans;
}
}
if(x!=1) ans=ans*(x-1);
return ans;
}
inline int read(int mod)//改进快读，让他边读边输入
{
//g用来判断b与phi(m)的大小，如果小于，就不能加了，这是坑点！
int x=0;
bool g=false;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^'0');
if(x>=mod) x%=mod,g=true;
c=getchar();
}
if(g) return (x+mod);
else return x;
}
int a,mod;
char b[20000005];
inline int quickpow(int a,int b)//快速幂
{
long long ans=1,base=(long long)a;
while(b)
{
if(b&1) ans=ans*base%mod;
b>>=1;
base=base*base%mod;
}
return (int)(ans%mod);
}
int p;
int main()
{
scanf("%d%d",&a,&mod);
int p=phi(mod);
int cishu=read(p);//得出的化简次数
int s=quickpow(a,cishu);
printf("%d\n",s);
return 0;
}
大概就这些啦，还有些高深点的东西以后再更。