题目链接
HDU-6265
思路
因为$\phi$函数是积性函数，所以他的和函数也是积性函数，所以我们分别算出每一个质数对它的贡献然后相乘即可。
这样就能对每一个进行计算答案了，注意当i=0的时候的答案需要另外算。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int md = 998244353;
ll quick_pow(ll a,ll b)
{
ll res=1;
a%=md;
while(b)
{
if(b&1)res=(res*a)%md;
b>>=1;
a=(a*a)%md;
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int m;
scanf("%d",&m);
ll ans = 1;
while(m--)
{
ll p,q;
scanf("%lld %lld",&p,&q);
ll res=1;
res=(((q*(p-1))%md*quick_pow(p,q-1)%md)%md+quick_pow(p,q))%md;
ans=(ans*res)%md;
}
cout<<ans<<endl;
}
}
|