python/TangDou/51NOD/1928.cpp

#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;
}