学步园

HDU_3923

    这个题目可以直接应用polya定理，但最后设计到一个带除法的表达式的取模问题。看了别人的解题报告后发现，应用完polya定理之后，需要计算的表达式就变成了ans/(2*m)%MOD，而2*m和MOD是互质的，所以可以先求出2*m关于模MOD的乘法逆元x，那么就有ans/(2*m)%MOD=ans*x/(2*m*x)%MOD=ans*x%MOD。

    暂时还不明白为什么这么做可以，就先当结论记下了。

#include<stdio.h>
#include<string.h>
#define D 1000000007
int N, M;
long long int pow_mod(int a, int n)
{
long long int ans;
if(n == 1)
return a % D;
    ans = pow_mod(a, n / 2);
    ans = ans * ans % D;
return (n & 1) ? ans * a % D : ans;
}
int gcd(int x, int y)
{
return y == 0 ? x : gcd(y, x % y);
}
void exgcd(long long int a, long long int b, long long int &x, long long int &y)
{
if(b == 0)
        x = 1, y = 0;
else
    {
        exgcd(b, a % b, y, x);
        y -= x * (a / b);
    }
}
void solve()
{
int i, j, k;
long long int ans = 0, x, y;
for(i = 0; i < M; i ++)
        ans = (ans + pow_mod(N, gcd(i, M))) % D;
if(M & 1)
        ans = (ans + M * pow_mod(N, M / 2 + 1)) % D;
else
        ans = (ans + M / 2 * pow_mod(N, M / 2) + M / 2 * pow_mod(N, M / 2 + 1)) % D;
    exgcd(2 * M, D, x, y);
    x = (x % D + D) % D;
    ans = (ans * x) % D;
    printf("%d\n", (int)ans);
}
int main()
{
int t, tt;
    scanf("%d", &t);
for(tt = 0; tt < t; tt ++)
    {
        scanf("%d%d", &N, &M);
        printf("Case #%d: ", tt + 1);
        solve();
    }
return 0;
}