Invoker

Problem Description
On of Vance's favourite hero is Invoker, Kael. As many people knows Kael can control the elements and combine them to invoke a powerful skill. Vance like Kael very much so he changes the map to make Kael more powerful.

In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.

Input
The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )

Output
For each test case: output the case number as shown and then output the answer mod 1000000007 in a line. Look sample for more information.

Sample Input
2
3 4
1 2

Sample Output
Case #1: 21
Case #2: 1

https://www.cnblogs.com/lxjshuju/p/6824210.html

这题就是用polya定理，由于要取模，而且要除于一个数，所有要逆元素。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MOD= 1e9+7;

long long pow_m(long long a,int n)
{
long long ret = 1;
long long temp = a%MOD;
while(n)
{
if(n&1)
{
ret = temp;
ret %= MOD;
}
temp *= temp;
temp %= MOD;
n >>= 1;
}
return ret;
}
int gcd(int a,int b)
{
if(b == 0)return a;
return gcd(b,a%b);
}
//*****************************
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
if(a==0&&b==0) return -1;//无最大公约数
if(b==0){x=1;y=0;return a;}
long long d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
long long mod_reverse(long long a,long long n)
{
long long x,y;
long long d=extend_gcd(a,n,x,y);
if(d==1) return (x%n+n)%n;
else return -1;
}

int main()
{
int T;
int m,n;
scanf("%d",&T);
int iCase = 0;
while(T--)
{
iCase++;
scanf("%d%d",&m,&n);
long long ans = 0;
if(n%2==0)
{
ans = n/2*pow_m(m,n/2)+n/2*pow_m(m,n/2+1);
ans %= MOD;
}
else ans = n*pow_m(m,n/2+1);
//cout<<ans<<endl;
for(int i = 0;i < n;i++)
{
ans += pow_m(m,gcd(i,n));
ans %= MOD;
//cout<<ans<<endl;
}
ans *= mod_reverse(2*n,MOD);
ans%=MOD;
printf("Case #%d: %I64d\n",iCase,ans);
}
return 0;
}

#include "stdio,h"
#include "string.h"
#include "algorithm"
#include "iostream"
#include "stdlib.h"
#include "time.h"
#include "math.h"

或者参考https://blog.csdn.net/sr_19930829/article/details/38125529?utm_source=tuicool&utm_medium=referral