题解 | #欧拉#

# 标题 欧拉（ 哦啦 ^-^ ）

考察对积性函数性质以及欧拉函数的应用，线性筛实现
首先从 “柿子” 开始分析：
欧拉函数：$\phi (n)={\sum }_{d\mathrm{\mid }n}d\mu (\frac{n}{d})\backslash varphi(n)\; =\; \backslash sum\_\{d|n\}\; d\; \backslash \; \backslash mu(\; \backslash frac\{n\}\{d\}\; )$ 是 积性函数 ，由 $\phi \ast I\backslash varphi\; *\; I$ （*表示狄利克雷卷积） 而来 ；
同理：$F(n)={\sum }_{d\mathrm{\mid }n}{d}^k\mu (\frac{n}{d})F(n)\; =\; \backslash sum\_\{d|n\}\; d^k\; \backslash \; \backslash mu(\; \backslash frac\{n\}\{d\}\; )$ 是由$\phi \ast I_{d(n)}\backslash varphi\; *\; I\_\{d(n)\}$ 而来 ；

观察“柿子”容易发现：

if( n = Prime ) : $F(n)=n^k-1F(n)\; =\; n^k\; -\; 1$ ;（类似欧拉函数性质）
esle :

if $gcd(a,b)=1gcd(\; a,b\; )\; =\; 1$ :
$F(a\ast b)=F(a)\ast F(b)\backslash quad\; F(\; a*b\; )\; =\; F(a)*F(b)$ ( 由积性函数性质易知 )
else :

首先我们考虑当 $n=p^{m}n\; =\; p^m$ 时 ，

$F(n)={\sum }_{d\mathrm{\mid }n}{d}^k\mu (\frac{n}{d})F(n)\; =\; \backslash sum\_\{d|n\}\; d^k\; \backslash mu(\backslash frac\{n\}\{d\})$
$=1\mu (p^m)+(p^k)\mu (p^{m-1})+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+(p^{m-1}{)}^k\mu (p)+(p^m{)}^k\mu (1)=\; 1\backslash mu(p^m)\; +\; (p^k)\backslash mu(p^\{m-1\})\; +\; ....\; +\; (p^\{m-1\})^k\; \backslash mu(p)\; +\; (p^m)^k\; \backslash mu(1)$
$=0+0+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+(p^{m-1}{)}^k\mu (p)+(p^m{)}^k\mu (1)=\; 0\; +\; 0\; +\; ....\; +\; (p^\{m-1\})^k\; \backslash mu(p)\; +\; (p^m)^k\; \backslash mu(1)$
$=(p^{mk})-(p^{m-1}{)}^k=\; (p^\{mk\})\; -\; (p^\{m-1\})^k$
$=(p^{m-1}{)}^k(p^k-1)=\; (p^\{m-1\})^k(p^k-1)$

其次我们考虑当 $n=a\ast p^w(gcd(a,p)==1)n\; =\; a\; *\; p^w\; \backslash qquad(\; gcd(a,p)\; ==\; 1\; )$
$F(n)=F(a)\ast F(p^w)F(n)\; =\; F(a)\; *\; F(p^w)$
$=F(a)\ast (p^{w-1}{)}^k\ast (p^k-1)=\; F(a)\; *\; (p^\{w-1\})^k\; *\; (p^k-1)$

$F(n\ast p)=F(a\ast p^{w+1})=F(a)\ast F(p^{w+1})F(n*p)\; =\; F(\; a*p^\{w+1\}\; )\; =\; F(a)\; *\; F(p^\{w+1\})$
$=F(a)\ast (p^w{)}^k\ast (p^k-1)=\; F(a)\; *\; (p^w)^k*(p^k-1)$
$=F(n)\ast p^k=\; F(n)\; *\; p^k$
$=F(n)\ast (F(p)+1)=\; F(n)\; *\; (\; F(p)\; +\; 1\; )$
$\therefore F(n\ast p)=F(n)\ast (F(p)+1)\backslash therefore\; F(n*p)\; =\; F(n)*(\; F(p)\; +\; 1\; )$

理论推导完毕!
接下来是代码：

const int N = 5e6+5;
const int Max = 998244353 ;
#define M  5000000
int m , k ;
int prime[N] ;
int ans[N] ;
bool vis[N] ;
void init()
{
	ans[1] = 1 ;
	int cnt = 0 ;
	for( int i = 2 ; i <= M ; ++ i ){
		if( !vis[i] ){
			prime[++cnt] = i ;
			ans[i] = QuickPow( i , k )-1 ;//QuickPow为快速幂 i^k%mod
		}
		for( int j = 1 ; j <= cnt && 1ll*i*prime[j] <= M ; ++ j ){
			vis[ i*prime[j] ] = 1 ;
			if( i % prime[j] == 0 ){
				ans[ i*prime[j] ] = ans[i] * ( ans[ prime[j] ] + 1 ) % Max ;
				break ;
			}
			else {
				ans[ i*prime[j] ] = ans[i] * ans[ prime[j] ] % Max;
			}
		}
	}
}

如有错误,欢迎留言指出
点个赞呗⁂((✪⥎✪))⁂**
附加：