【polya+Euler】HDU 2239 机器人的项链

KIDx的解题报告

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2239

 

题意：这个项链有n个的珠子组成，珠子的类型有m种，请问能组成多少种不同类型的项链（若一个项链可以通过另一个项的链旋转得到，那么认为这两个项链为同一种项链）。答案可能很大，请对9937取模

 

解析：先由polya定理得到：

ans = sum(m^gcd (i, n), i∈(1, n)) / n;

由于n太大（1<n<2^31），不能直接for循环求

要用到欧拉函数：

首先要搞明白phi(n/i)表示1~n有多少个数跟n的最大公约数是i

然后就问题就转换成：枚举n的约数，例如是p那么1~n中与n最大公约数为p的就有phi(n/p)个，把这种情况累计到res中：res+= phi(n/p) * (m^p);

 

累计完后，因为是边累计边取余，而且后面要除以n

本来逆元就行了，但是题目是有问题的，有些数据是不存在逆元的，是不能出答案的，但是hdu的结果是求最小的数。。。

所以这里利用等式res/n % mod = ans---> res% mod = ans*n% mod，从0~9936枚举ans找到最小满足的答案即可。。。

 

#include <iostream>
#include <math.h>
using namespace std;
#define M 66000
#define LL __int64

int p[6600], k, vis[M] = {0}, mod = 9937;

int Euler (int n)
{
    int i, res = n;
    for (i = 0; i < k && (LL)p[i]*p[i] <= n; i++)
    {
        if (n % p[i] == 0)
        {
            do
            n /= p[i];
            while (n % p[i] == 0);
            res = res - res/p[i];
        }
    }
    if (n > 1) res = res - res/n;
    return res % mod;
}

int qmod (int a, int b)
{
    a %= mod;
    int res = 1;
    for ( ; b; b >>= 1)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

int main()
{
    int n, m, i, j, ms, ans;
    k = 0;
    for (i = 2; i < M; i++)
    {
        if (!vis[i])
        {
            p[k++] = i;
            for (j = i+i; j < M; j+=i)
                vis[j] = 1;
        }
    }
    while (~scanf ("%d%d", &n, &m))
    {
        ms = (int)sqrt (n+0.5);
        ans = 0;
        for (i = 1; i <= ms; i++)
        {
            if (n % i == 0)
            {
                ans = (ans + Euler (n/i)*qmod (m, i)%mod) % mod;
                if (i != n/i) ans = (ans + Euler (i)*qmod (m, n/i)%mod) % mod;
				//不要忘了还有右边的约数n/i要枚举
            }
        }
        int tot = ans;
        for (ans = 0; ans < mod; ans++)
            if ((LL)ans*n % mod == tot % mod)
                break;
        printf ("%d\n", ans);
    }
    return 0;
}