Master of Phi (欧拉函数 + 积性函数的性质 + 狄利克雷卷积)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6265

题目大意:首先T是测试组数,n代表当前这个数的因子的种类,然后接下来的p和q,代表当前这个数的因子中含有p的q次方.然后让你求题目第一行给你的信息.

 首先理一下思路.

第一步,我们需要算题目中要求的公式(第一行),首先,他是一个积性函数,所以我们先将题目中的第一行的式子命名为F(n).对于F(n),我们可以分着求他的每一个因子的解,然后最终将这一写乘起来就可以了.

F(n) = F(p1^q1)*F(p2^q2)........*F(pn^qn).这是积性函数的一个性质.

(积性函数的介绍:https://baike.baidu.com/item/%E7%A7%AF%E6%80%A7%E5%87%BD%E6%95%B0/8354949?fr=aladdin)

第二步,我们开始化简这个式子.中间会运用到 欧拉函数的性质.

(欧拉函数的介绍:https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0)

 

第一步,因为题目中给定的因数都是大于1的,所以需要对1单独讨论,然后到了第三行,利用欧拉函数的一个性质,

当f(x)中,x为 质数p的k次幂的时候,f(x)=(p-1)*p^(k-1).

然后其他顺着推下来就可以了.

最后就是将所有因子算出来的结果相乘就可以了(注意取模的位置).

AC代码:

 1 #include<iostream>
 2 #include<cmath>
 3 #include<string>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<stdio.h>
 7 using namespace std;
 8 # define ll long long
 9 # define inf 0x3f3f3f3f
10 const int maxn =100000+100;
11 # define ll long long
12 # define mod 998244353
13 struct node
14 {
15     ll x,y;
16 } q[maxn];
17 ll quickpow(ll t1,ll t2)
18 {
19     if(t2==0)return 1;
20     t2--;
21     ll ans=t1;
22     while(t2)
23     {
24         if(t2&1)ans=ans*t1%mod;
25         t1=t1*t1%mod;
26         t2>>=1;
27     }
28     return ans%mod;
29 }
30 int main()
31 {
32     int T;
33     cin>>T;
34     while(T--)
35     {
36         int n;
37         cin>>n;
38         for(int i=1; i<=n; i++)
39         {
40             cin>>q[i].x>>q[i].y;
41         }
42         ll ans=1;
43         for(int i=1; i<=n; i++)
44         {
45             ll temp=quickpow(q[i].x,q[i].y-1);
46             ans=ans*temp%mod*(q[i].x+(q[i].x-1)*q[i].y%mod+mod)%mod;
47         }
48         cout<<ans<<endl;
49     }
50     return 0;
51 }
52 
53