题解：AT_abc414_e [ABC414E] Count A%B=C

· · 题解

题意

求满足 a \mod b = c 且 1\le a,b,c \le n 的 (a,b,c) 的个数 (3 \le n \le 10^{12})

思考

先考虑枚举 a，因为 c \ge 1 ，所以 a \mod b \neq 0 ，即 b 不是 a 的因数。

所以每个 a 对应的个数为 a - ( a 的因数个数 )。

两部分分开计算，第一部分的和是 \frac{n(n+1)}{2} 应该没人不会吧，

重点在第二部分，

相当于求 b | a , 1 \le a , b \le n 的 (a,b) 个数

也就是对于每个 b 求其倍数个数，即

\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor

答案为

\frac{n(n+1)}{2}-\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor

于是变成了数论分块的模板，时间复杂度 O(\sqrt n) 。

数论分块（学过的可以跳过了）

用于求 \sum_{i=1}^{n}f(i)g(\lfloor\frac{n}{i}\rfloor) 的 O(\sqrt n) 算法

具体求区间的方法：每次根据上一个区间确定 $l$，则 $$r = \lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$$ **证明：** 设 $ \lfloor\frac{n}{l}\rfloor = k

则对于区间中的任意一个数 j， j \times k \le n

故 j\le \lfloor\frac{n}{k}\rfloor = \lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor =r

代码

#include<bits/stdc++.h>
using namespace std;
long long n,mod=998244353;

int main()
{
    scanf("%lld",&n);
    long long ans=((__int128)n)*(n+1)/2%mod;
    long long i;
    for(i=1;i*i<=n;i++)ans=(ans+mod-n/i%mod)%mod;
    for(long long l=i,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans=(ans+mod-(r-l+1)%mod*(n/l)%mod)%mod;
    }
    printf("%lld",ans);
}