You are given positive integers n(n≤109),m(m≤2×109),p(p≤2×109)n ( n \le 10^9), m ( m \le 2 \times 10^9), p(p \le 2 \times 10^9)n(n≤109),m(m≤2×109),p(p≤2×109) and you need to calculate the following product modulo ppp.

∏i=1n∏j=1n∏k=1nmgcd⁡(i,j)[k∣gcd⁡(i,j)]\displaystyle \displaystyle\prod_{i = 1}^n \displaystyle\prod_{j = 1}^n \displaystyle\prod_{k = 1}^n m^{\gcd(i,j)[k|\gcd(i,j)]}i=1∏nj=1∏nk=1∏nmgcd(i,j)[k∣gcd(i,j)]

Input

Each test file contains a single test case. In each test file:

There are three positive integers n,m,pn, m, pn,m,p which are separated by spaces. It is guaranteed that ppp is a prime number.

Output

An integer representing your answer.

样例输入1复制 

2 2 1000000007

样例输出1复制 

128

样例输入2复制 

233 131072 4894651

样例输出2复制 

748517

样例输入3复制 

1000000000 999999997 98765431

样例输出3复制 

50078216
  • main.cpp
    • 代码高亮 Sublime Vim Emacs
    环境配色亮色配色暗色配色
    暗色配色

    返回

    • 亮色配色
    • 暗色配色
    代码缩进248
    4

    返回

    • 2
    • 4
    • 8
                                                                     C++ 语言 (C++11)                                                                 C++ 语言 (C++14)                                                                 C 语言                                                                 Java 语言                                                                 Python 语言 (2.7)                                                                 Python 语言 (3.5)
    C++ 语言 (C++11)

    返回

    • C++ 语言 (C++11)
    • C++ 语言 (C++14)
    • C 语言
    • Java 语言
    • Python 语言 (2.7)
    • Python 语言 (3.5)
通用
逻辑
循环
数学
文本
列表
颜色
变量
函数 
x
 ans+=(2*djsphi(n/l)%mod-1+mod)%mod*((cal(r)-cal(l-1)+mod)%mod)%mod;
39 
 {
40 
 phi[i*prim[j]]=phi[i]*(prim[j]-1);
41 
 d[i*prim[j]]=d[i]*d[prim[j]];
42 
 a[i*prim[j]]=1;
43 
 }
44 
 }
45 
 }
46 
 for(int i=1;i<maxn;i++)
47 
 sum2[i]=sum2[i-1]+phi[i];
48 
 for(int i=1;i<maxn;i++)
49 
 sum[i]=(sum[i-1]+(ll)i*d[i]%mod)%mod;
50
51 
}
52 
ll cal(ll n)
53 
{
54 
 if(n<maxn)
55 
 return sum[n];
56 
 if(w2.count(n)==1)
57 
 return w2[n];
58 
 ll ans=0;
59 
 for(ll l=1,r;l<=n;l=r+1)
60 
 {
61 
 r=n/(n/l);
62 
 ans+=((l+r)*(r-l+1)/2)%mod*((n/l)*(n/l+1)/2%mod)%mod;
63 
 ans%=mod;
64 
 }
65 
 w2[n]=ans;
66 
 return ans;
67 
}
68
69 
ll djsphi(ll x)
70 
{
71 
 if(x<maxn)
72 
 return sum2[x];
73 
 if(w1.count(x)==1)
74 
 return w1[x];
75 
 ll ans=(x)*(x+1)/2;
76 
 for(ll l=2,r;l<=x;l=r+1)
77 
 {
78 
 r=x/(x/l);
79 
 ans-=(r-l+1)*djsphi(x/l);
80 
 }
81 
 return w1[x]=ans;
82 
}
83 
ll qpow(ll a,ll n)
84 
{
85 
 ll ans=1;
86 
 while(n)
87 
 {
88 
 if(n&1)
89 
 ans=ans*a%mod;
90 
 a=a*a%mod;
91 
 n>>=1;
92 
 }
关闭终端 终端 - 计蒜客 



	#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+10;
typedef  long long ll;
ll mod=1e9+7;
bool vis[maxn];
int phi[maxn];
ll sum2[maxn];
ll sum[maxn];
ll d[maxn];
ll a[maxn];
int cnt,prim[maxn];
unordered_map<ll,ll>w1;
unordered_map<ll,ll>w2;
void get(int maxn)
{
    phi[1]=1;
    d[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            d[i]=2;
            a[i]=1;
            prim[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&prim[j]*i<maxn;j++)
        {
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)
            {
                phi[i*prim[j]]=phi[i]*prim[j];
                d[i*prim[j]]=d[i]/(a[i]+1)*(a[i]+2);
                a[i*prim[j]]=a[i]+1;
                break;
            }
            else
            {
                phi[i*prim[j]]=phi[i]*(prim[j]-1);
                d[i*prim[j]]=d[i]*d[prim[j]];
                a[i*prim[j]]=1;
            }
        }
    }
    for(int i=1;i<maxn;i++)
        sum2[i]=sum2[i-1]+phi[i];
    for(int i=1;i<maxn;i++)
        sum[i]=(sum[i-1]+(ll)i*d[i]%mod)%mod;





	}
ll cal(ll n)
{
    if(n<maxn)
       return sum[n];
    if(w2.count(n)==1)
        return w2[n];
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans+=((l+r)*(r-l+1)/2)%mod*((n/l)*(n/l+1)/2%mod)%mod;
        ans%=mod;
    }
    w2[n]=ans;
    return ans;
}





	ll djsphi(ll x)
{
    if(x<maxn)
        return sum2[x];
    if(w1.count(x)==1)
        return w1[x];
    ll ans=(x)*(x+1)/2;
    for(ll l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=(r-l+1)*djsphi(x/l);
    }
    return w1[x]=ans;
}
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1)
            ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int main()
{





	    ll n,m,p;
    cin>>n>>m>>p;
    mod=p-1;
    get(maxn);
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans+=(2*djsphi(n/l)%mod-1+mod)%mod*((cal(r)-cal(l-1)+mod)%mod)%mod;
        ans%=mod;
    }
    mod=p;
    printf("%lld",qpow(m,ans));
    return 0;
}