[HDU]5728 PowMod

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Problem Description

Declare $$k=\sum ^m _{i=1} \phi(i*n) mod \space 1e9+7$$.

$$n$$ is a square-free number.

$$\phi$$ is the $$Euler's \space totient \space function$$.

Find:$$ans=k^{k^{k \cdots }} \space mod \space p$$.

There are infinite number of $$k$$.

Input

Multiple test cases($test \space cases ≤100$), one line per case.

Each line contains three integers, n,m and p.

$1≤n,m,p≤10^7$

Output

For each case, output a single line with one integer, ans.

Sample Input

1 2 6
1 100 9

Sample Output

4
7

Source

2016 Multi-University Training Contest 1

题解

题目大意

计算k:

$$k=\sum ^m _{i=1} \phi(i \cdot n) \mod \space 1e9+7$$

算k的无限个k次方对p取mod的值

过程

计算k:

欧拉函数是积性函数，有两条性质：

(1).积性函数性质:

$$F(m_1 \cdot m_2)=F(m_1) \cdot F(m_2)$$,

当且仅当$$m_1,m_2$$互质时成立。

(2).$$\phi(p \cdot k \cdot n)=p \cdot \phi(k \cdot n )$$,其中，p是n的素因子。

那么假设素数p是n的一个素因子，显然$$gcd(p,n/p)=1$$;关键是$$i$$，如果$$i$$中没有素因子$$p$$，那么就直接用积性性质。如果$$i \space mod \space p=0$$，必然可以写成$$i=k \cdot p$$;即倍数关系，否则$$i \space mod \space p\neq 0$$;所以分成两部分求:

对于(1)($$i \space mod \space p \neq 0$$) (积性函数性质)

$$\sum {i \mod p \neq 0} ^m \phi (i·\frac{n}{p}p)= \phi (p)· \sum ^m {i \mod p \neq 0} \phi (i \frac{n}{p}) \tag{I}$$

对于(2)($$i \space mod \space p =0$$)根据等式$$i=k \cdot p$$及欧拉函数通式

$$\sum {kp}^m \phi(kp·n)=p· \sum {kp} ^m \phi (kn) (k=1,2,3...) =p \cdot \sum ^{ \frac{m}{p}} _{i=1} \phi (i \cdot n)\ \ \ \ \ \tag{II}$$

又$$\because p=\phi(p)+1$$,再将$${I}与{II}相加$$：

$$f(n,m)= \phi (p)[ \sum {i \mod p \neq 0} \phi (i \frac{n}{p})+ \sum {i=1} ^{ \frac{m}{p}} \phi (i \cdot n) \space ] + \sum _{i=1} ^{ \frac{m}{p}} \phi (i \cdot n ) \tag{III}$$

注意到$$x = y$$中是可以合并的

$$\because \sum ^{ \frac{m}{p}} {i=1} \phi (i \cdot n)= \sum ^m {i \mod p=0} \phi (i \cdot n \cdot \frac{1}{p})$$

$$\therefore f(n,m)=\phi(p)\sum_{i=1}^m\phi (i \cdot \frac{n}{p})+ \sum _{i=1} ^{\frac{m}{p}}\phi (i \cdot n) \tag{IV}$$

$$IV$$即：

$$f(n,m)= \phi (p)·f( \frac{n}{p},m)+f(n, \frac{m}{p})$$

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e7+5;
int fi[maxn],t,pri[maxn/10];
int sumfi[maxn];
bool flag[maxn];
void pre()
{
    t=0;memset(flag,0,sizeof(flag));
    fi[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!flag[i]){
            pri[t++]=i;
            fi[i]=i-1;
        }
        for(int j=0;j<t&&i*pri[j]<maxn;j++)
        {
            flag[i*pri[j]]=1;
            if(i%pri[j]==0) {
                fi[i*pri[j]]=fi[i]*pri[j];
                break;
            }
            fi[i*pri[j]]=fi[i]*(pri[j]-1);
        }
    }
    sumfi[1]=fi[1];sumfi[0]=0;
    for(int i=2;i<maxn;i++)
    {
        sumfi[i]=sumfi[i-1]+fi[i];
        if(sumfi[i]>=mod) sumfi[i]-=mod;
    }
}
int q[50],top;
struct SS
{
    int a,b,c;
    SS (int _a=0,int _b=0,int _c=0):a(_a),b(_b),c(_c){};
    bool operator <  (const SS &y) const
    {
        if(a!=y.a) return a<y.a;
        if(b!=y.b) return b<y.b;
        return c<y.c;
    }
};
map<SS,int> mp;
int getk(int i,int m,int now)
{
    if(mp[SS(i,m,now)]) return mp[SS(i,m,now)];
    if(i==top) return sumfi[m];
    if(m==0) return 0;
    return mp[SS(i,m,now)]=(1LL*getk(i+1,m,now/q[i])*(q[i]-1)+getk(i,m/q[i],now))%mod;
}
long long fast(int ci,long long num,int tmod)
{
    long long ans=1;
    while(ci)
    {
        if(ci&1) ans=ans*num%tmod;
        num=num*num%tmod;ci=ci>>1;
    }
    return ans;
}
int extgcd(int a, int b, int & x, int & y,int tmod)
{
    if (b == 0) { x=1; y=0; return a; }
    int d = extgcd(b, a % b, x, y,tmod);
    int t = x; x = y; y = (t - 1LL*a / b * y)%tmod;
    if(y<tmod) y+=tmod;
    return d;
}
int solve(int k,int p)
{
    if(p==1) return 0;
    if(k==1) return 1;
    int tmp=1;
    for(int i=0;i<top;i++)
    {
        while(p%q[i]==0){
            tmp=tmp*q[i];
            p=p/q[i];
        }
    }
    if(p==1) return 0;
    int t=solve(k,fi[p]);
    if(tmp==1){
        return fast(t,k,p);
    }
    int tt=fast(t,k,p);
    int x,y;
    extgcd(tmp,p,x,y,p*tmp);
    return 1LL*x*tmp%(p*tmp)*tt%(p*tmp);
}
int main()
{
    int n,m,p;
    pre();
    while(scanf("%d%d%d",&n,&m,&p)!=EOF)
    {
        top=0;
        int tn=n;mp.clear();
        for(int i=0;i<t&&1LL*pri[i]*pri[i]<=n;i++)
        {
            if(n%pri[i]==0){
                q[top++]=pri[i];n/=pri[i];
            }
        }
        if(n>1){
            q[top++]=n;
        }
        int k=getk(0,m,tn);
        tn=k;
        top=0;
        for(int i=0;i<t&&1LL*pri[i]*pri[i]<=k;i++)
        {
            if(k%pri[i]==0){
                q[top++]=pri[i];
                while(k%pri[i]==0)
                k/=pri[i];
            }
        }
        if(k>1) q[top++]=k;
        printf("%d\n",solve(tn,p));
    }
    return 0;
}

[HDU]PowMod