China remainder theorem (Bài toàn Hàn Tín điểm binh)

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
//China remainder theorem
using namespace std;
int n;
long long a[11][2], mod = 1, sum = 0;
int Phi(int p)
{
    int phi = p;
    for (int i = 2; i * i <= p; ++ i)
    {
        if (p % i == 0)
        {
            while (p % i == 0)
            {
                p/= i;
            }
            phi -= phi/i;
        }
    }
    if (p != 1)
    {
        phi -= phi/p;
    }
    return phi;
}
long long power(long long x, long long y, long long p)
{
    if (y == 0)
    {
        return 1;
    }
    long long t = power(x, y/2, p);
    if (y % 2 == 0)
    {
        return (t * t) % p;
    }
    else
    {
        return ((t * t) % p * x) % p;
    }
}
void read()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i][0] >> a[i][1];
        mod *= a[i][1];
    }
}
void solve()
{
    for (int i = 1; i <= n; ++ i)
    {
        long long N = 1;
        for (int j = 1; j <= n; ++ j)
        {
            if (i != j)
            {
                N *= a[j][1];
            }
        }
        sum += a[i][0] * (power(N, Phi(a[i][1]) - 1, a[i][1])) * N;
        sum %= mod;
    }
    cout << sum;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen(TASK".INP", "r", stdin);
    freopen(TASK".OUT", "w", stdout);
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        read();
        solve();
    }
}