POJ 1365 Prime Land——质数分解

POJ 1365 Prime Land——质数分解

注意用longlong

#include #include #include #include #include typedef long long ll;using namespace std;const int maxn = 1e5;ll ipow(ll x, ll y) { ll ans = 1; while (y) { if (y & 1) ans *= x; x *= x; y >>= 1; } return ans;}bool isprime[maxn];int prime[maxn], cnt;void creatprime() { memset(isprime, true, sizeof(isprime)); cnt = 0; for (long long i = 2; i < maxn; i++) { if (isprime[i] == true) { prime[++cnt] = i; for (long long j = 2 * i; j < maxn; j += i) isprime[j] = false; } }}int num, P[maxn], E[maxn];void fenjie(ll x) { num = 0; memset(E, 0, sizeof(E)); for (int i = 1; i <= cnt && x > 1; i++) { if (x % prime[i]) continue; P[++num] = prime[i]; while (x > 1 && x % prime[i] == 0) { E[num]++, x /= prime[i]; } }}void output() { int flag = 0; for (int i = num; i >= 1; i--) { if (flag++) printf(" "); printf("%d %d", P[i], E[i]); } printf("\n");}int main() { creatprime(); char c; int p, e; ll sum = 1; while (~scanf("%d", &p) && p) { scanf("%d", &e); c = getchar(); sum *= ipow(p, e); if (c == '\n') { fenjie(sum - 1); output(); sum = 1; } } return 0;}

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