B4118 题解

luogu_gza · 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 了。