44 lines
1.1 KiB
C++
44 lines
1.1 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef pair<int, int> PII;
|
||
vector<PII> g;
|
||
// 判断一个数是不是质数
|
||
bool isPrime(int n) {
|
||
if (n < 2) return false;
|
||
for (int i = 2; i <= n / i; i++)
|
||
if (n % i == 0) return false;
|
||
return true;
|
||
}
|
||
|
||
int main() {
|
||
int k;
|
||
cin >> k;
|
||
int a = 1;
|
||
while (k--) {
|
||
int p, m;
|
||
cin >> p >> m;
|
||
a *= pow(p, m);
|
||
}
|
||
a--;
|
||
|
||
int last = -1;
|
||
|
||
for (int i = 2; i * i <= a; i++) { // 遍历所有小因子
|
||
if (a % i > 0 || !isPrime(i)) continue; // 不是因子 或者 不是质数
|
||
|
||
// 如果数字a除以这个质数因子i,商a/i也是一个质数因子，它是最后一个最大的质数因子,只能有1个
|
||
if (isPrime(a / i) && a / i > i) last = a / i;
|
||
|
||
int x = a;
|
||
int cnt = 0;
|
||
while (x % i == 0) {
|
||
cnt++;
|
||
x /= i;
|
||
}
|
||
if (cnt > 0) g.push_back({i, cnt});
|
||
}
|
||
if (~last) g.push_back({last, 1});
|
||
for (int i = g.size() - 1; i >= 0; i--)
|
||
cout << g[i].first << " " << g[i].second << endl;
|
||
return 0;
|
||
} |