CCPC-2017 杭州站B丨HDU - 6265丨数论丨积性函数 丨欧拉函数丨狄利克雷卷积丨思维变换

【参考博客】@WJHKDGHP ccpc2017杭州站 B
【参考博客】@灬从此以后灬 2017 CCPC 杭州 HDU6265B 积性函数
特别感谢以上两位博主，让我看懂了许多细节。

交题网址（HDU-6265）
题意：依次输入一个整数分解质因数的各项底数与指数，求算：

∑d|nφ(d)×nd$\sum _{d|n}\phi (d)\times \frac{n}{d}$
思路：（其实最开始还有些数学常识的不足，比如d|n 表示 “d可整除n”，也就是n的因子）

首先狄利克雷识破三连：
1. 如果你见过狄利克雷卷积：(f×g)(n)=∑d|nf(d)×g(nd)$(f\times g)(n)=\sum _{d|n}f(d)\times g(\frac{n}{d})$
2. 又知道两个积性函数的狄利克雷卷积也是积性函数。
3. 还知道欧拉函数和f(x)=x$f(x)=x$都是积性函数 。
那么就可以“一眼看出”积性函数：

h(d)=∑d|nφ(d)×nd$h(d)=\sum _{d|n}\phi (d)\times \frac{n}{d}$

由于积性函数的特性：h(d)=∏mi=1h(pqii)$h(d)=\prod _{i=1}^{m}h(p_i^{q_i})$ 这就契合输入的格式，下面要解决的是就是如何求h(pq)$h(p^q)$。
由题给公式可以得到：(p是质数（n的质因子），d所有可取的值有{1,p,p2,⋯,pq}$\{1,p,p^2,\cdots ,p^q\}$)

h(pq)=∑d|pqφ(d)×pqd=∑qi=0φ(pi)×pq−i$h(p^q)=\sum _{d|p^q}\phi (d)\times \frac{p^q}{d}=\sum _{i=0}^q\phi (p^i)\times p^{q-i}$

欧拉函数有：（注意* k=0的时候是不满足的）

φ(pk)=pk(1−1p)$\phi (p^k)=p^k(1-\frac{1}{p})$
【证明参阅】Value for a prime power argument
于是我们可以进一步化解：
h(pq)=pq+∑qi=1pi(1−1p)×pq−i$h(p^q)=p^q+\sum _{i=1}^q{p}^i(1-\frac{1}{p})\times p^{q-i}$
=pq+pq−1(p−1)⋅q$=p^q+p^{q-1}(p-1)·q$
到此，我们可以得到计算答案的公式了：ans=∏pq+pq−1(p−1)⋅q$ans=\prod p^q+p^{q-1}(p-1)·q$ (略去了i)
也就是说每次输入一组 p和q，计算结果累乘到答案上即可！
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 89444;
typedef long long ll;
const ll mod = 998244353;
int T;

ll fpow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1)ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}

int main()
{
    int T,m;
    ll q,p,ans,tmp;
    scanf("%d",&T);
    while(T--)
    {
        ans=1;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%lld%lld",&p,&q);
            tmp=1;
            tmp=tmp*(p-1)%mod;
            tmp=tmp*q%mod;
            tmp=tmp*fpow(p,q-1)%mod;
            tmp=(tmp+fpow(p,q))%mod;
            ans=ans*tmp%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
/*
2
2
2 1
3 1
2
2 2
3 2
*/