POJ - 2154 Color——Polya+欧拉函数优化

POJ - 2154 Color——Polya+欧拉函数优化

ans = 1/n*∑(0<=i && i < n)(n^gcd(i, n))

= 1/n*∑(0<=i && i < n && n%i == 0)(euler(i) * n^i)

= ∑(0<=i && i < n && n%i == 0)(euler(i) * n^(i-1))

#include #include #include #include using namespace std;typedef long long ll;int euler(int x) { int ans = x; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { ans = ans / i * (i - 1); while (x % i == 0) x /= i; } } if (x > 1) ans = ans / x * (x - 1); return ans;}ll ipow(ll a, int n, int mod) { ll ans = 1; while (n) { if (n & 1) ans = (ans * a) % mod; a = (a * a) % mod; n >>= 1; } return ans;}int main() { int x, n, p; scanf("%d", &x); while (x--) { scanf("%d%d", &n, &p); ll ans = 0; for (int i = 1; i * i <= n; i++) { if (i * i == n) ans = (ans + ipow(n, i-1, p)*euler(i)) % p; else if (n % i == 0) { ans = (ans + ipow(n, i-1, p)*euler(n/i) + ipow(n, n/i-1, p) * euler(i)) % p; } } printf("%lld\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。