问题为：然后就可以用线性筛递推以后用整数分块计算答案。#include <bits/stdc++.h> const int MAXN = 1e7; using namespace std; int T,n,m,cnt; int p[MAXN+5],g[MAXN+5],a[MAXN+5],b[MAXN+5]; bool vis[MAXN+5]; inline void in...
问题为： \begin{align*} 若k != 1\ g(p) &= p^k-p^{k-1}-(p^{k-1}-p^{k-2})\\ g(p) &= p^k-2p^{k-1}+p^{k-2}\\ g(p) &= (p-1)^2p^{k-2}\\ \end{align*}这样的话就可以用线性筛递推求得g(n)#include <bits/stdc++.h> const int...