题解：AT_abc414_e [ABC414E] Count A%B=C
bz029
·
·
题解
解题思路
由于余数 c 于 a,b 密切相关，且当 a,b 一定时，c 是唯一的，确定的。因此在统计答案是不需要枚举 c。
为了防止数对重复，我们规定：a>b>c。
再由题面知，1\le c，即 c 不能为 0，也就是 a 不能是 b 的倍数的情况都成立。所以我们只要知道 (a,b)（b\le a）的所有可能对数 sum 和 (a,b) 中 b\mid a（b 能整除 a，b\le a）的对数 ans。最终答案就是 sum-ans。
解释一下上面为什么 a 可以与 b 相等：是因为当 a=b 时，b\mid a 成立所以它在 sum 和 ans 里都统计了一次，在最终答案里抵消了相当于没统计，所以上面的 a 可以与 b 相等。
但是 $ans$ 就比较难在 1s 计算了，它的计算需要使用“数论分块”算法。在此，我就不~~献丑~~介绍了。不会的同学可以学习 [P3935 Calculating](https://www.luogu.com.cn/problem/P3935) 及其[题解](https://www.luogu.com.cn/problem/solution/P3935)，它告诉了我们，如何在 $\sqrt{N}$ 的时间里求出 $1$ 到 $N$ 内的约数个数和。
代码如下：
```cpp
for(int l=1,r;l<=N;l=r+1){
r=N/(N/l);
ans+=(N/r)%mod*((r-l+1)%mod)%mod;
ans%=mod;
}
```
最后只要注意取模并统计答案就行了。
时间复杂度：$O(\sqrt{N})$。
### 赛时代码
代码很短，不含注释只有 300 多 Byte。
```cpp
#include<bits/stdc++.h>
#define int long long//记得开long long
using namespace std;
const int mod=998244353;//记得取模
int N,ans;
signed main(){
cin>>N;
for(int l=1,r;l<=N;l=r+1){//统计约数对数
r=N/(N/l);
ans+=(N/r)%mod*((r-l+1)%mod)%mod;
ans%=mod;
}
int sum;//统计所有可能对数
if(N%2) sum=(N+1)/2%mod*(N%mod)%mod;
else sum=N/2%mod*((N+1)%mod)%mod;
cout<<(sum-ans+mod)%mod;//输出答案
return 0;
}
```