首页 > 代码库 > poj 2154 Color
poj 2154 Color
这是道标准的数论优化的polya题。卡时卡的很紧，需要用int才能过。程序中一定要注意控制不爆int！！！我因为爆intWA了好久=_=……
题目简洁明了，就是求 sigma n^gcd(i,n)；但是由于n很大，所以直接暴力枚举必然会T。于是我们按照这种题的通常思路按gcd的值分类。
gcd(i, n) = 1 的个数很明显为 phi(n);
gcd(i, n) = 2 -> gcd(i/2, n/2) = 2 所以个数为 phi(n/2);
这样就ok了， 我们就是要求 sigma phi(n/d) * n^d ， 其中 d 是 n 的因数。
上代码：
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>using namespace std;int n, p;int mi(int a){ int ans = 1, zan = n%p; while (a) { if (a & 1) ans = (ans * zan) % p; a >>= 1; zan = (zan * zan) % p; } return ans;}int ouler(int now){ int ans = now; for (int i = 2; i*i <= now; ++i) if (!(now % i)) { ans = ans / i * (i-1); while (!(now % i)) now /= i; } if (now > 1) ans = ans / now * (now-1); return ans;}int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &p); int ans = 0; for (int i = 1; i*i <= n; ++i) if (!(n % i)) { ans = (ans + ouler(n/i)%p*mi(i-1)) % p; // 两个函数位置一定不能倒过来 if (i * i != n) ans = (ans + ouler(i)%p*mi(n/i-1)) % p; // 不然会超int！！！ } printf("%d\n", ans % p); } return 0;}
poj 2154 Color
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。