HDU 6051 If the starlight never fade【原根】【推公式】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6051
AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll m,p;
ll Eulr(ll x)
{
    ll ans=x;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            ans=ans*(i-1)/i;
            while(x%i==0)
            {
                x/=i;
            }
        }
    }
    if(x>1)
        ans=ans*(x-1)/x;
    return ans;
}
ll qpow(ll x,ll y ,ll mo)
{
    ll ans=1;
    while(y>0)
    {
        if(y%2==1)
        {
            ans=(ans*x)%mo;
        }
        x=(x*x)%mo;
        y>>=1;
    }
    return ans;
}
ll hanshu(ll d,ll n)
{
    ll ans=d * d % mod * ((n * Eulr(n) + (n == 1)) / 2) % mod;
     //ll ans=((d*d%mod)*Eulr(p/d)%mod*p/d+(d==1))*qpow(2,mod-2,mod);
     return ans;
}
int main()
{
    int t;
    int Case=0;
    cin>>t;
    while(t--)
    {
        cin>>m>>p;
        p-=1;
        ll ans=0;
        for(ll i=1;i*i<=p;i++)
        {
            if(p%i==0)
            {
                    ans=(ans+hanshu(i,p/i))%mod;
                    if(i*i!=p)
                        ans=(ans+hanshu(p/i,i))%mod;
            }
        }
        ll sum=((p+1)*p/2)%mod;
        ans=((ans-sum)%mod+mod)%mod;
        ans=(ans*m)%mod;
        printf("Case #%d: %lld\n",++Case,ans);
    }
    return 0;
}

我一定可以的！！！