本文主要是介绍POJ 2154 Color (ploya欧拉函数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
ploya定理，然后公式利用欧拉函数优化，gcd必然是因子，这样只要枚举因子，每个因子利用欧拉函数计算出现次数
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int t, n, p;int pow_mod(int x, int k) {x %= p;int ans = 1;while (k) {if (k&1) ans = ans * x % p;x = x * x % p;k >>= 1;}return ans;
}int phi(int n) {int ans = n;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {ans = ans / i * (i - 1);while (n % i == 0) n /= i;}}if (n > 1) ans = ans / n * (n - 1);return ans % p;
}int main() {scanf("%d", &t);while (t--) {scanf("%d%d", &n, &p);int ans = 0;for (int i = 1; i * i <= n; i++) {if (n % i == 0) {ans = (ans + pow_mod(n, i - 1) * phi(n / i) % p) % p;if (n / i != i) {int tmp = n / i;ans = (ans + pow_mod(n, tmp - 1) * phi(n / tmp) % p) % p;}}}printf("%d\n", ans);}return 0;
}
这篇关于POJ 2154 Color (ploya欧拉函数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
