专栏首页数据结构与算法POJ2154 Color(Polya定理)

POJ2154 Color(Polya定理)

Time Limit: 2000MS

Memory Limit: 65536K

Total Submissions: 11654

Accepted: 3756

Description

Beads of N colors are connected together into a circular necklace of N beads (N<=1000000000). Your job is to calculate how many different kinds of the necklace can be produced. You should know that the necklace might not use up all the N colors, and the repetitions that are produced by rotation around the center of the circular necklace are all neglected.  You only need to output the answer module a given number P. 

Input

The first line of the input is an integer X (X <= 3500) representing the number of test cases. The following X lines each contains two numbers N and P (1 <= N <= 1000000000, 1 <= P <= 30000), representing a test case.

Output

For each test case, output one line containing the answer.

Sample Input

5
1 30000
2 30000
3 30000
4 30000
5 30000

Sample Output

1
3
11
70
629

Source

POJ Monthly,Lou Tiancheng

Polya定理:

假设$G$是$p$个对象的一个置换群,用$m$种颜色涂染$p$个对象,则不同颜色的方案数为

$L = \frac{1}{|G|}\sum_{g_i \in G}m^{c(g_i)}$

$G = \{g_1, g_2, \dots g_s \}$,$c(g_i)$为置换$g_i$的循环节数

本题而言第$i$种置换的循环节数为$gcd(n, i)$

因此答案为$L = \frac{1}{n}\sum_{i = 1}^n n^{gcd(i, n}$

枚举约数,用欧拉函数计算,时间复杂度$O(T\sqrt(N) f(n))$,$f(n)$表示小于$\sqrt(n)$的质因子的个数

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#define LL long long  
const int MAXN = 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int T, N, mod;
int fastpow(int a, int p, int mod) {
    int base = 1; a %= mod;
    while(p) {
        if(p & 1) base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base % mod;
}
int prime[MAXN], tot, vis[MAXN];
void Prime() {
    for(int i = 2; i <= MAXN - 10; i++) {
        if(!vis[i]) prime[++tot] = i;
        for(int j = 1; j <= tot && prime[j] * i <= MAXN - 10; j++) {
            vis[i * prime[j]] = 1;
            if(!i % prime[j]) break;
        }
    }
}
int phi(int x, int mod) {
    int limit , ans = x;
    for(int i = 1; i <= tot && prime[i] * prime[i] <= x; i++) {
        if(!(x % prime[i])) {
            ans = ans - ans / prime[i];
            while((x % prime[i]) == 0) x /= prime[i];
        }
    }
    if(x > 1) ans = ans - ans / x;  
//    printf("%d", ans % mod);
    return ans % mod;
}
main() {
    T = read();
    Prime();
    while(T--) {
        N = read(); mod = read(); 
        int ans = 0, now = N;
        for(int d = 1; d * d<= N; d++) {
            if(d * d == N)    
                ans = (ans + fastpow(N, d - 1, mod) % mod * phi(N / d, mod) % mod) % mod;
            else if( (N % d) == 0) {
                ans = (ans + fastpow(N, d - 1, mod) * phi(N / d, mod) + fastpow(N, N / d - 1, mod) * phi(d, mod)) % mod;
            }
                
            //printf("%d\n", ans);
        }
        //if(now > 0) ans += fastpow(N, now - 1, mod) * phi(N / now, mod);
        printf("%d\n", ans % mod);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ3734 Blocks(生成函数)

    任意的是\(e^x\),偶数的是\(\frac{e^x + e^{-x}}{2}\)

    attack
  • BZOJ2693: jzptab(莫比乌斯反演)

    122 HINT T <= 10000 N, M<=10000000

    attack
  • BZOJ4766: 文艺计算姬

    Description "奋战三星期,造台计算机"。小W响应号召,花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺 术细胞。普通计算机能计算一个带...

    attack
  • POJ3734 Blocks(生成函数)

    任意的是\(e^x\),偶数的是\(\frac{e^x + e^{-x}}{2}\)

    attack
  • BZOJ2693: jzptab(莫比乌斯反演)

    122 HINT T <= 10000 N, M<=10000000

    attack
  • 2019 牛客暑期多校训练营 第四场 C sequence 区间问题

    用户2965768
  • Codeforces Round #674 (Div. 3) A ~ F 详细讲解

    思路+题意:就是除了第一层有两个单元的话,其余的楼层都有x个单元。自己动手推一推就知道了。然后就是取余跟做除,看看在当前这层,还是下一层。不要忘了 加上第一层。

    用户7727433
  • Codeforce-Ozon Tech Challenge 2020-C. Kuroni and Impossible Calculation(鸽笼原理)

    To become the king of Codeforces, Kuroni has to solve the following problem.

    风骨散人Chiam
  • 数论-GCD、LCM、扩展欧几里得

    给定若干区间的GCD,试还原原数组。 贪心乘最小的数使得区间内每个数是ans[i]的倍数(LCM),最后再检查一遍。

    唔仄lo咚锵
  • P3373 【模板】线段树 2 区间求和 区间乘 区间加

    题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输...

    attack

扫码关注云+社区

领取腾讯云代金券