Master of Phi(数论)

You are given an integer n. Please output the answer of   modulo 998244353. n is represented in the form of factorization.

φ(n) is Euler’s totient function, and it is defi ned more formally as the number of integers k in the interval 1≤k≤n for which the greatest common divisor gcd(n,k) is equal to 1.
For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all co-prime to 9, but the other three numbers in this interval, 3, 6, and 9 are not, because gcd(9,3) = gcd(9,6) = 3 and gcd(9,9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the interval from 1 to n is 1 itself, and gcd(1,1) = 1.
And there are several formulas for computing φ(n), for example, Euler’s product formula states like:

where the product is all the distinct prime numbers (p in the formula) dividing n.

输入

The fi rst line contains an integer T (1≤T≤20) representing the number of test cases.
For each test case, the fi rst line contains an integer m(1≤m≤20) is the number of prime factors.
The following m lines each contains two integers pi and qi (2≤pi≤108 , 1≤qi≤108 ) describing that n contains the factor piqi , in other words, . It is guaranteed that all pi are prime numbers and diff erent from each other.

输出

For each test case, print the the answer modulo 998244353 in one line.

思路：1.所要求的式子是狄利克雷卷积，是积性函数。 因此我们可以分着求他每一个因子的解，然后分成乘起来就可以了。

2.此外，在化简过程中我们还需要用到欧拉函数的性质：若N是质数p(即N=p), φ(n)= φ(p)=p-p^(k-1)=p-1。欧拉函数

以下是化简过程： 

# include <iostream>
# include <cstdio>
# include <cmath>
# include <algorithm>
# include<queue>
#define inf 0x3f3f3f3f
# define ll long long
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn =100000+100;
# define ll long long
# define mod 998244353
struct node
{
    ll x,y;
} q[maxn];
ll ppow(ll a,ll b)
{
    if(b==0)return 1;
    b--;
    ll ans=a;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
int main()
{
    int t,n;
    ll ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            cin>>q[i].x>>q[i].y;
        }
        ans=1;
        for(int i=1; i<=n; i++)
        {
            ll temp=ppow(q[i].x,q[i].y-1);
            ans=((ans*temp)%mod*(q[i].x+(q[i].x-1)*q[i].y%mod+mod)%mod)%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}