UVA 10892 LCM Cardinality——质因分解

UVA 10892 LCM Cardinality——质因分解

#include #include #include #include #include #define OUT freopen("out.txt", "w", stdout)using namespace std;const int maxn = 1e5 + 10;bool isprime[maxn];int prime[maxn], primecnt;void init() { memset(isprime, true, sizeof(isprime)); primecnt = 0; for (int i = 2; i < maxn; i++) { if (isprime[i]) { prime[++primecnt] = i; for (int j = i * 2; j < maxn; j += i) isprime[j] = false; } }}int p[maxn], cnt;void breakdown(int x) { cnt = 0; for (int i = 1; i <= primecnt && x > 1; i++) { if (x % prime[i]) continue; ++cnt; while (x % prime[i] == 0 && x > 1) { p[cnt]++; x /= prime[i]; } } if (x > 1) p[++cnt] = 1;}int main() { //OUT; init(); int n; while (~scanf("%d", &n) && n) { memset(p, 0, sizeof(p)); breakdown(n); long long ans = 1; for (int i = 1; i <= cnt; i++) { ans *= (long long)2 * p[i] + 1; } ans = (ans + 1) / 2; printf("%d %lld\n", n, ans); } return 0;}

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