题目：

参考：

　　　

好像这样复杂度就是 \( O(n\sqrt{n} \) 的了。

#include
      
       #include
       
        #include
        
         using namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}const int N=1e5+5,mod=1e9+7;int upt(int x){
    if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}int n,a[N];void init(){  int n=1e5; a[0]=1;  for(int i=1;i<=n;i++)    for(int j=1;;j++)      {    int k0=j*(3*j-1)>>1, k1=j*(3*j+1)>>1;    int fx=(j&1)?1:-1;    if(k0>i&&k1>i)break;    if(k0<=i)a[i]=upt(a[i]+fx*a[i-k0]);    if(k1<=i)a[i]=upt(a[i]+fx*a[i-k1]);      }}int main(){  int T=rdn(); init();  while(T--)    n=rdn(),printf("%d\n",a[n]);  return 0;}
        
       
      

 关于 hdu 4658 ：

大概就是原来是 \( P(x)*\phi(x) = 1 \) ，现在是 \( P_k(x) = \frac{\phi(x^k)}{\phi(x)} = \phi(x^k)*P(x) \)

每次想求 \( P_k(x) \) 的第 n 项系数，所以先把 \( P(x) \) 预处理出来，然后每次暴力算 \( P_k(x) \) 的第 n 项，就是 \( O(n\sqrt{n}) \) 了。

#include
      
       #include
       
        #include
        
         using namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}const int N=1e5+5,mod=1e9+7;int upt(int x){
    if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}int p[N];void init(){  int n=1e5; p[0]=1;  for(int i=1;i<=n;i++)    for(int j=1;;j++)      {    int k0=j*(3*j-1)>>1, k1=j*(3*j+1)>>1;    int fx=(j&1)?1:-1;    if(k0>i&&k1>i)break;    if(k0<=i)p[i]=upt(p[i]+fx*p[i-k0]);    if(k1<=i)p[i]=upt(p[i]+fx*p[i-k1]);      }}int solve(){  int n=rdn(),k=rdn(),ans=p[n];  for(int i=1;;i++)    {      int k0=k*i*(3*i-1)>>1, k1=k*i*(3*i+1)>>1;      int fx=(i&1)?-1:1;      if(k0>n&&k1>n)break;      if(k0<=n)ans=upt(ans+fx*p[n-k0]);      if(k1<=n)ans=upt(ans+fx*p[n-k1]);    }  printf("%d\n",ans);}int main(){  init(); int T=rdn();  while(T--)solve();  return 0;}