题目链接: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
查看更多关于【卷积神经网络】的文章
