出题人题解 | #欧拉#

原题解链接：https://ac.nowcoder.com/discuss/149984

$idk(n)=n^K,\mu (n)i\; d\; k(n)=n^\{K\},\; \backslash mu(n)$ 为积性函数

其中 $idk(x)i\; d\; k(x)$ 为完全积性函数

发现这个式子为这两个函数的狄利克雷卷积,那么 $F(x)F(x)$ 也是一个积性函数考虑进行线性简

若 $(a,b)=1(a,\; b)=1$ 那么 $F(ab)=F(a)\ast F(b)F(a\; b)=F(a)\; *\; F(b)$

若 $(a,b)!=1(a,\; b)\; !=1$ 考虑只一个质数 $p_{i}p\_\{i\}$ 构成的情况

只需要考虑为单个质数的情况,后面的 $\mu \backslash mu$ 函数值为 0 了

那么 $F\left(p_i^{k_i}\right)={\left(p_i^{k_i}\right)}^K+\mu \left(p_i\right)\times {\left(p_i^{k_i-1}\right)}^{K}F\backslash left(p\_\{i\}^\{k\_\{i\}\}\backslash right)=\backslash left(p\_\{i\}^\{k\_\{i\}\}\backslash right)^\{K\}+\backslash mu\backslash left(p\_\{i\}\backslash right)\; \backslash times\backslash left(p\_\{i\}^\{k\_\{i\}-1\}\backslash right)^\{K\}$

所以 $F(p_i^{k_i}\times p_i)=F\left(p_i^{k_i}\right)\times p_i^{k}F\backslash left(p\_\{i\}^\{k\_\{i\}\}\; \backslash times\; p\_\{i\}\backslash right)=F\backslash left(p\_\{i\}^\{k\_\{i\}\}\backslash right)\; \backslash times\; p\_\{i\}^\{k\}$

对于 $p_i{p}_{j}p\_\{i\}\; p\_\{j\}$ 不同的情况,直接乘起来就好了

#include<cstdio> 
#include<bits/stdc++.h> 
#include<algorithm> 
inline int read() { 
     int x = 0,f = 1 ; 
     char c = getchar(); 
     while(c < '0' || c > '9')c = getchar(); 
     while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); 
     return x * f; 
} 
const int mod = 998244353;  
int t,k; 
const int maxn = 5000007; 
int num,p[maxn],mu[maxn],F[maxn],tmp[maxn]; 
bool np[maxn]; 
int fstpow(int x,int k) {
    int ret = 1; 
    for(;k;k >>= 1,x = 1ll * x * x % mod) 
        if(k & 1) ret = 1ll * ret * x % mod; 
    return ret; 
} 
void pre(int k) { 
    F[1] = mu[1] = 1; 
    for(int i = 2;i <= 5000000;++ i) { 
        if(!np[i]) p[++ num] = i, mu[i] = -1, tmp[num] = fstpow(i,k),F[i] = (tmp[num] - 1) % mod; 
        for(int t,j = 1;j <= num && i * p[j] <= 5000000;++ j) { 
            t = i * p[j]; 
            np[t] = 1; 
            if(i % p[j]) mu[t] = -mu[i],F[t] = 1ll * F[i] * F[p[j]] % mod; 
            else mu[t] = 0,F[t] = 1ll * F[i] * tmp[j] % mod; 
        } 
    } 
} 
int main() { 
    	t = read(),k = read(); 
    	pre(k); 
    	for(int n,i = 1;i <= t;++ i) { 
       	 n = read(); 
    	    printf("%d\n",F[n]);   
   		 } 
//	} 
    return 0; 
}