召唤师·卡尔（Polya定理）- HDU 3923

Polya定理是为了解决环状组合计数的问题，比如，对于一个有5颗珠子的环形手链，给你2种颜色对珠子上色，能够得到多少种不同的手链呢？

显然，题意看起来比较好理解，但是要解决这个问题却很麻烦。对于5颗珠子上色，我们直接全部列出，是这样的：

（5颗珠子2种颜色涂色）

这个问题二十世纪初才得到解决，数学家Polya在前人的基础上整理了一个公式，以后做题直接用公式算数量就好了。公式如下：

好吧，是不是一脸懵逼，看了公式也不知道写代码。没办法，数学就是这样深奥，做题的时候直接套用模板函数代码好了，不细讲。

本篇你如果学到了Polya定理的使用场合就OK了！

但是如果你是专业NOI或者ACM队员，希望你还是看相关专业书籍深入去理解，对于你们来说，不只是计算机理论，数学理论也是必修的。

来看题~

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.

游戏Dota里面，文斯最喜欢的英雄是召唤师·卡尔。卡尔这个英雄能够操控元素，通过组合各种元素来施放强大的技能。文斯制作了一张变态图，这张地图里卡尔能够控制更多元素而异常变态。

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.

在这个新地图里，卡尔能够操控n种元素，他能够将m种元素围成一圈组成一个技能。但是如果这个m个元素通过旋转或者反转，算作重复，不会产生新技能。

那么卡尔能够组合多少种技能呢？

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 )

第一行是测试用例个数。

每个用例输入n和m。

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

解题思路：

1、和珠子上色一样的逻辑。

2、直接调用公式~

3、本题实现中采用质数表、欧拉函数进行了优化。

源代码：G++ 0ms HDU排名41

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define MOD 1000000007
#define LL long long
using namespace std;

/***************************************************/
static int prime[30] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
                 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101
                };
int cnt = 25;

//欧拉公式
LL Eular(LL num)
{
    LL ret = 1;
    for (int i = 0; i < cnt && prime[i] <= num; i++)
        if (num % prime[i] == 0) {
            ret *= (prime[i] - 1);
            num /= prime[i];
            while (num % prime[i] == 0) {
                num /= prime[i];
                ret *= prime[i];
            }
        }

    if (num > 1)
        ret *= (num - 1);
    return ret % MOD;
}

//求指数
LL Pow(LL a, LL b) {
    LL ret = 1;
    while (b) {
        if (b & 1)
            ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }

    return ret;
}

//Polya公式
LL Polya(int m, int n) {
    LL sum = 0, i;
    for (i = 1; i * i < n; i++) {
        if (n % i == 0) {
            sum = (sum + Eular(i) * Pow(m, n / i)) % MOD;
            sum = (sum + Eular(n / i) * Pow(m, i)) % MOD;
        }
    }
    if (i * i == n)
        sum = (sum + Eular(i) * Pow(m, i)) % MOD;

    if (n & 1)
        sum = (sum + n * Pow(m, n / 2 + 1)) % MOD;
    else
        sum = (sum + n / 2 * (Pow(m, n / 2) + Pow(m, n / 2 + 1))) % MOD;

    return (sum * Pow(2 * n, MOD - 2)) % MOD;
}
/***************************Polya end****************************/

int main()
{
    LL m, n;
    LL t, cas = 0;
    scanf("%I64d", &t);
    while (t--) {
        scanf("%I64d%I64d", &m, &n);
        //直接调用公式求解
        printf("Case #%I64d: %I64d\n", ++cas, Polya(m, n));
    }
    return 0;
}