@Junlier
2018-11-08T16:56:22.000000Z
字数 2446
阅读 4821
数学方法——数论
阅读体验:https://zybuluo.com/Junlier/note/1300214
这年头不总结一下是真的容易忘,老了老了,要AFO了。。。
欧拉函数写做,表示到中与互质的数的个数
那么我们会有引理(对于素数):
我们可以用线性筛素数的方法同时把欧拉函数筛出来(根据上面的引理)
不会线性筛素数?那你把这个板子背了就会了。。。笑哭.
(去掉和数组有关的就是线性筛素数了)
背板子吧,其实也容易理解
void Prepare_Phi()
{
phi[1]=1;
for(int i=2;i<=M;++i)
{
if(!phi[i])pri[++tot]=i,phi[i]=i-1;//①
for(int j=1;j<=tot;++j)
{
if(i*pri[j]>M)break;
if(!(i%pri[j]))
{
phi[i*pri[j]]=phi[i]*pri[j];//②
break;
}else phi[i*pri[j]]=phi[i]*(pri[j]-1);//③
}
}
}
il lst euler(rg lst x)
{
rg lst ans=x,tp=sqrt(x);
for(lst i=2;i<=tp;++i)
if(x%i==0)
{
ans=ans-ans/i;
while(x%i==0)x/=i;
}
if(x>1)ans=ans-ans/x;
return ans;
}
有了欧拉函数做坚实的后盾
讲欧拉定理就不用扯那些七里八里的东西了
一个公式:当互质时
最有用的?
PS:结合后面的扩展欧拉定理可以用作降幂,后面讲
嗯,一般扩展不就是把互质推广到所有情况嘛
行,如果上面那个式子里面不互质了
根据上面两个定理的公式结合起来
#include<bits/stdc++.h>
#define lst long long
#define ldb double
#define N 10000050
#define M 10000000
using namespace std;
const int Inf=1e9;
int read()
{
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int Q,tot;
int phi[N],pri[N];
void Prepare_Phi()
{
phi[1]=1;
for(int i=2;i<=M;++i)
{
if(!phi[i])pri[++tot]=i,phi[i]=i-1;//①
for(int j=1;j<=tot;++j)
{
if(i*pri[j]>M)break;
if(!(i%pri[j]))
{
phi[i*pri[j]]=phi[i]*pri[j];//②
break;
}else phi[i*pri[j]]=phi[i]*(pri[j]-1);//③
}
}
}
lst qpow(lst x,lst y,lst mod)
{
lst ret=1;
while(y)
{
if(y&1)ret=ret*x%mod;
x=x*x%mod,y>>=1;
}return ret;
}
lst Solve(lst mod)
{
if(mod==1)return 0;
return qpow(2,Solve(phi[mod])+phi[mod],mod);
}
int main()
{
Prepare_Phi();
Q=read();
while(Q--)
{
int p=read();
printf("%lld\n",Solve(p));
}
return 0;
}
那,讲完了啊。。。你以为能讲多少。。。
毕竟我是个菜鸡嘛