hdu 6051 If the starlight never fade

复健复健。。。
标题和题目似乎没什么关系。。。

显然$(x+y)^i\equiv x^i\mod p$左右两边都不能为0。
设$p$的原根为$d$，$x+y\equiv d^b\mod p,x\equiv d^a\mod p$。
有：
$d^{bi}\equiv d^{ai}\mod p$
$i(b-a)\equiv 0\mod \phi(p)$
显然，$b-a=\frac {\phi(p)} {(\phi(p),i)}k|k\in[1,(\phi(p),i)-1]$。
那么，设$b-a$任意一个解为$z$：
$d^a+y\equiv d^{a+z}\mod p$
$x+y\equiv xd^z\mod p$
$yx^{-1}\equiv d^z-1\mod p$
$x\equiv y(d^z-1)^{-1}\mod p$
因为$z$必然模$\phi(p)$不为0，所以每一个$y$都存在$(\phi(p),i)-1$个对应的$x$。
即：$f(i)=m((\phi(p),i)-1)$。

结果为：
$m(\sum_{i=1}^{\phi(p)}i(\phi(p),i)-\sum_{i=1}^{\phi(p)}i)$
枚举gcd，有：
$\sum_{i=1}^{p-1}i(p-1,i)=\sum_{k|p-1}k^2\frac{\phi(\frac {p-1} k)\frac {p-1} k+[k=p-1]} 2$
直接计算即可，复杂度为$O(\sqrt plogp)$。

#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<cmath>
using namespace std;
#define clr(a) memset(a,0,sizeof(a))
//--Container
//
typedef long long ll;
const ll md=1e9+7;
inline ll qni(ll a,ll b){ll r=1;for(;b;b>>=1,a=a*a%md)if(b&1)r=r*a%md;return r;};
const ll _2=qni(2,md-2);

ll rs;int p[30][2],pd;
void _qs(int n){
    int i,j,d=sqrt(n);for(i=2,pd=0;i<=d&&n>1;++i)if(!(n%i)){
        for(p[pd][1]=0,p[pd][0]=i;!(n%i);n/=i)p[pd][1]++;++pd;
    }
    if(n>1){p[pd][0]=n,p[pd][1]=1;++pd;}
};

void _dfs(int ts,int k,int n,int d){
    if(d==pd)
        rs=(rs+(ll)(n/k)*(n/k)%md*((ll)ts*k%md+(k==1?1:0))%md*_2%md);
    else{
        _dfs(ts,k,n,d+1);int i;for(i=1,k*=p[d][0],ts*=(p[d][0]-1);i<=p[d][1];++i){
            _dfs(ts,k,n,d+1);
            ts*=p[d][0],k*=p[d][0];
        }
    }
};
int ct=0;
void _cl(int n,int m){
    int i,j;_qs(n-1);rs=0;_dfs(1,1,n-1,0);rs=(rs+md-((ll)n*(n-1)%md*_2%md))%md;rs=rs*m%md;
    printf("Case #%d: %I64d\n",++ct,rs);
};
void cl(){
    int n,m;scanf("%d %d",&m,&n);_cl(n,m);
};

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int t;scanf("%d",&t);while(t--)cl();
    return 0;
};