QOJ3231

luogu_gza · 2025-02-07 16:49:34 · 个人记录

有一小部分没拍进去，\mu(\frac nd)=-1 是乘上了 \frac{1}{1-x^d}。

然后暴力做背包即可。

//0:01背包1:完全背包
void calc(int n)
{
  t0.clear(),t1.clear();
  for(int i=1;i*i<=n;i++) if(n%i==0)
  {
    if(mu[i]==1) t0.pb(n/i);
    if(mu[i]==-1) t1.pb(n/i);
    if(i*i!=n)
    {
      if(mu[n/i]==1) t0.pb(i);
      if(mu[n/i]==-1) t1.pb(i);
    }
  }
  ans[n].resize(phi[n]+1);
  ans[n][0]=1;
  for(auto j:t0) rep(i,phi[n],j) ans[n][i]-=ans[n][i-j];
  for(auto j:t1) fo(i,j,phi[n]) ans[n][i]+=ans[n][i-j];
  vis[n]=1;
}

为啥别人写的这么菜，我都最优解了兄弟们!!!!