c088: 00516 - Prime Land
Tags: factor
出處:https://zerojudge.tw/ShowProblem?problemid=c088
提交:https://zerojudge.tw/Submissions?problemid=c088&account=allllllan123456
問題:給定一個大於 2 且不超過 32767 的正整數的標準分解式,請輸出它減一之後的標準分解式,並且以降冪排列 (大質數者在前)。
解法:這題其實就是 a010 的進階版,比較難搞的地方在於降冪排列,所以要先把質數和次方存進陣列裡,之後再倒過來印。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int p, t, arr[15], arr2[15]; string line;
6 while (getline(cin, line) && line!="0") { istringstream iss(line);
7 int n=1, arrL=0, cnt=0;
8 while (iss >> p >> t)
9 while (t--) n *= p;
10 n--; p=2;
11 while (true)
12 if (n % p) {
13 if (cnt) arr[arrL] = p, arr2[arrL++] = cnt;
14 p++; cnt = 0;
15 if (n == 1) break;
16 } else n /= p, cnt++;
17 while (arrL--)
18 cout << arr[arrL] << ' ' << arr2[arrL] << ' ';
19 cout << '\n';
20 }
21 return 0;
22}