2019-07-19 18:48 西南科技大学客户端其它

关注

西安邀请赛 B Product

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复制

样例输入2复制

233 131072 4894651

样例输出2复制

样例输入3复制

1000000000 999999997 98765431

样例输出3复制

50078216

main.cpp

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)

通用

逻辑

循环

数学

文本

列表

颜色

变量

函数

 ans+=(2*djsphi(n/l)%mod-1+mod)%mod*((cal(r)-cal(l-1)+mod)%mod)%mod;

 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;

关闭终端终端 - 计蒜客

编辑代码


	#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;
}