```cpp
rep(i,1,1e6)
for(int j=i;j<=1e6;j+=i){
if(mu[j/i]==1)g[j]=(1LL*g[j]*f[i])%mod;
else if(mu[j/i]==-1)g[j]=(1LL*g[j]*inv(f[i]))%mod;
}
```
中`inv(f[i])`是固定的,可以预处理
不预处理该段代码的时间复杂度为 $O(n\log^2n)$
by TianTian2008 @ 2022-09-20 07:13:44
@[TianTian2008](/user/244009) 谢谢
by lao_li @ 2022-09-20 12:34:40