様々な実装方針が考えられると思いますが、その内の \(1\) つを紹介します。

まず、全ての \(P_i\) について \(N\) が \(P_i^{S_i}\) で割り切れるような最小の \(N\) を見つけます。

これは、二分探索を用いることで解くことができます。

この時に \(N = 10^{18}\) としても全ての \(P_i\) について \(N\) が \(P_i^{S_i}\) で割り切れなければ、-1 を出力します。

後は、求めた値が条件と矛盾しないかを見ればよいです。

計算量は \(O(M log N)\) です。

想定解(C++)

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

bool hantei1(long long X,int M,vector<long long>P,vector<long long>S) {
    for(int i = 0; i < M; i++) {
        long long cnt = 0,tmp = P[i];
        while (tmp <= X) {
            cnt += X/tmp;
            if(X/P[i] >= tmp) tmp *= P[i];
            else break;
        }
        if(cnt < S[i]) return false;
    }
    return true;
}

bool hantei2(long long X,int M,vector<long long>P,vector<long long>S) {
    for(int i = 0; i < M; i++) {
        long long cnt = 0,tmp = P[i];
        while (tmp <= X) {
            cnt += X/tmp;
            if(X/P[i] >= tmp) tmp *= P[i];
            else break;
        }
        if(cnt != S[i]) return false;
    }
    return true;
}

long long inf = 1000000000000000000;

int main() {
    int M;
    cin >> M;
    vector<long long>P(M),S(M);
    for(int i = 0; i < M; i++) {
        cin >> P[i] >> S[i];
    }
    if(!hantei1(inf,M,P,S)) {
        cout << -1 << endl;
        return 0;
    }
    long long l = 0,r = inf;
    while (l+1 < r) {
        long long mid = (l+r)/2;
        if(hantei1(mid,M,P,S)) r = mid;
        else l = mid;
    }
    if(!hantei2(r,M,P,S)) {
        cout << -1 << endl;
        return 0;
    }
    cout << r << endl;
}