裸的模板题，除2n的时候用了一下费马小定理
费马小定理：
特别的，当p为素数时，x无法被p整除，φ(p)=p-1，于是便有费马小定理Xp-1≡1(mod p)
在p是素数时，对任意正整数x都有Xp≡X(mod p)
于是对于a的逆元x，有ax≡1(mod m),对于a,m互素且m为素数时，有x=am-2，于是我们可以通过快速幂快速求出a的逆元。
另外，借助素数筛，我们还可以很快的求出1-n的欧拉函数值。每当我们找到一个素数，就把他的倍数的欧拉函数值乘上（p-1）/p.
而且，借助费马小定理我们可以实现对除法取模。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define LL long long
const LL mod = 1e9+7;
LL pow_mod(LL a,LL b)
{
LL s = 1;
while(b)
{
if(b&1)
s = (s*a)%mod;
a = (a*a)%mod;
b = b>>1;
}
return s;
}
LL polya(LL m,LL n)
{
LL i,ans = 0;
for(i=1;i<=n;i++)
{
ans += pow_mod(m,__gcd(i,n));
}
if(n&1) ans += n*pow_mod(m,n/2+1);
else ans += n/2*pow_mod(m,n/2) + n/2*pow_mod(m,n/2+1);
ans = ans%mod * pow_mod(2*n,mod-2)%mod;
return ans;
}
int main()
{
int T;
int cas = 1;
scanf("%d",&T);
while(T--)
{
int m,n;
scanf("%d%d",&m,&n);
printf("Case #%d: %d\n",cas++,polya(m,n));
}
}
