HDU 5728 PowMod 数论欧拉函数

2016 Multischool-Training-1-1006

题目链接

思路：

首先，考虑到\(\varphi\)是一个积性函数，我们有下面两条性质

\(\varphi (mn)=\varphi (m)\cdot \varphi (n)）\quad (m,n)=1\)
\(\varphi (pn)=p\cdot \varphi (n)\quad (p,\frac { n }{ p } )=1\) (p为n的一个质因子)

我们先来证明一下第二点

\[\begin{align}\varphi (pn) &=\varphi ({ p }^{ 2 }\cdot \frac { n }{ p } )\\ &=\varphi ({ p }^{ 2 })\cdot \varphi (\frac { n }{ p } )\\ &=p\cdot (p-1)\cdot \varphi (\frac { n }{ p } )\\ &=p\cdot \varphi (p)\cdot \varphi (\frac { n }{ p } )\\ &=p\cdot \varphi (n)\end{align}\]

题目中中说明\(n\)是square-free number，即表明它的每种质因子最多只有一个，因此我们来统计每个质因子对\(k\)的贡献:

所求\(k=\sum_{i=1}^{m} \varphi (i*n)\) 可先将\(n\)分解质因子，对于每个质因子\(p\)来说，若\((i,p)=1\)则直接由第一条性质拆出来即可，若\(i=kp\)，则由第二条性质，\(\varphi (kpn)=p\cdot \varphi (kn)\)，因此对质因子p有

\[\begin{align}\sum _{ i=1 }^{ m }{ \varphi (i\cdot n) } { | }_{ p } &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ i=kp }^{ i=1:m }{ \varphi (i\cdot n) } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot p\cdot n) } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n)\cdot p } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n)\cdot (\varphi (p)+1) } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n)\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n) } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ i\%p=0 }^{ i=1:m }{ \varphi (\frac { i }{ p } \cdot n)\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n) } \\ &=\sum _{ i=1 }^{ m }{ \varphi (i\cdot \frac { n }{ p } ) } +\sum _{ i=1 }^{ m/p }{ \varphi (i\cdot n) } \end{align}\]

所以我们可以递归求出\(k\)

得到\(k\)后，最后的答案只需要降幂公式降幂即可，\(k\)的无穷次方终将在递归中降成\(\%1\)的状态

\[{ A }^{ B }\%C={ A }^{ B\%\varphi (C)+\varphi (C) }\%C\]

比赛中也是找了好多办法求k都没求出来，最后也是参照大牛的博客的方法才知道怎么求的k

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
#define LL long long
const int MOD=1e9+7;
const int N=1e7+7;
LL phi[N],sum[N],pri[N];
int top,tp;
LL fac[100];
LL n,m,p;
bool vis[N];

LL mul(LL a,LL b, LL c)
{
    a%=c;
    b%=c;
    LL ret=0;
    while(b){
        if(b&1) (ret+=a)%=c;
        (a<<=1)%=c;
        b>>=1;
    }
    return ret;
}
LL pow(LL x,LL n,LL mod)
{
    x%=mod;
    if(n==1) return x;
    LL tmp=x,ret=1;
    while(n){
        if(n&1) ret=mul(ret,tmp,mod);
        tmp=mul(tmp,tmp,mod);
        n>>=1;
    }
    if(ret==0) ret+=mod;
    return ret;
}
void init()
{
    memset(vis,0,sizeof(vis));
    top=0;
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]) {
            pri[top++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<top&&i*pri[j]<N;j++){
            vis[i*pri[j]]=1;
            if(!(i%pri[j])){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }else phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    sum[0]=0;
    for(int i=1;i<N;i++)
        sum[i]=(sum[i-1]+phi[i])%MOD;
}
void getfac(LL n)
{
    tp=0;
    for(int i=0;i<top;i++){
        LL p1=pri[i];
        if(n%p1==0){
            fac[tp++]=p1;
            n/=p1;
        }
        if(!vis[n]){
            fac[tp++]=n;
            return;
        }
    }
}


LL sol(LL k,LL p,LL add) 
{
    if(p==1) return 1ll;
    LL tmp=sol(k,phi[p],phi[p]);
    return pow(k,tmp,p)+add;
}
LL  calc(int i,LL n,LL m)
{
    if(n==1) return sum[m];
    if(m==0) return 0;
    LL pp=fac[i];
    LL k=((pp-1)*calc(i+1,n/pp,m)%MOD+calc(i,n,m/pp))%MOD;
    return k;
}
int main(){
    init();
    while(~scanf("%lld%lld%lld",&n,&m,&p)){
        getfac(n);
        LL k=calc(0,n,m);
        LL ans=sol(k,p,0);
        printf("%lld\n",ans%p);
    }
    return 0;    
}