自动搬运

查看原文

来自洛谷，原作者为

	luogu_gza 猫猫怎么这么可爱

搬运于2025-08-24 21:17:14，当前版本为作者最后更新于2025-01-05 13:30:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑枚举 $1 \sim N$ 的所有数即可。

void main(){
  int n,a,b,ans=0;
  cin>>n>>a>>b;
  fo(i,1,n) if((i%a==0)+(i%b==0)==1) ans++;
  cout<<ans;
}

复杂度 $O(N)$。

然后我们考虑怎么把标爆掉。

转化为 $A$ 进制，然后记 $f(i,j,0/1)$ 表示当前填到了第 $i$ 位，模 $B$ 为 $j$，是否贴着上限（$N$）。

数位 dp，直接转移即可，复杂度 $O(AB \log N)$。

这个是个蠢做法。

当然，答案也是 $\lfloor \frac NA \rfloor+\lfloor \frac NB \rfloor-2\lfloor \frac N{AB} \rfloor$，这样就可以做到 $\max(\log A,\log B) \max(\log \log A,\log \log B)\log N$ 了。