C++(g++ 7.5.0) 解法, 执行用时: 7ms, 内存消耗: 460K, 提交时间: 2023-07-15 19:15:45

#include<bits/stdc++.h>
using namespace std;
void solve() {
	int k;
	cin>>k;
	int n=1;
	for (int i=0; i<k; i++) {
		int p,e;
		cin>>p>>e;
		for (int j=0; j<e; j++) {
			n*=p;
		}
	}
	n--;
	vector<int> p,e;
	int num=-1;
	for (int i=2; i<=n; i++) {
		if (n%i==0) {
			n/=i;
			p.push_back(i);
			e.push_back(1);
			num++;
		}
		while (n%i==0) {
			n/=i;
			e[num]++;
		}
	}
	for (int i=num; i>=0; i--) {
		cout<<p[i]<<" "<<e[i]<<" ";
	}
	cout<<endl;
}
int main(void) {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while (t--)
		solve();
	return 0;
}

C++ 解法, 执行用时: 8ms, 内存消耗: 416K, 提交时间: 2022-06-05 21:57:31

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int k; cin >> k;
  int n = 1; 
  while (k--) {
    int p, e; cin >> p >> e;
    while (e--) n *= p;
  }
  n--;
  map<int, int> cnt;
  for (int i = 2; i * i <= n; ++i) {
    for (; n % i == 0; n /= i) cnt[i]++;
  }
  if (n > 1) cnt[n]++;
  for (auto it = cnt.rbegin(); it != cnt.rend(); ++it) {
    auto [k, v] = *it;
    cout << k << ' ' << v << ' ';
  }
  cout << endl;
}

int main() {
  int t; cin >> t;
  while (t--) solve();
}

Python3 解法, 执行用时: 134ms, 内存消耗: 4656K, 提交时间: 2023-05-29 17:55:12

T=int(input())
for t in range(T):
    k=int(input())
    L=list(map(int,input().split()))
    n=1
    for i in range(k):
        n*=L[2*i]**L[2*i+1]
    n-=1
    l=[]
    for j in range(2,n+1):
        x=0
        while n%j==0:
            x+=1
            n//=j
        if x>0:
            l.append(x)
            l.append(j)
    l.reverse()
    for X in l:
        print(X,end=' ')
    print()