专栏文章

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

HHRS_ren_zheng_hang
AT_abc414_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miowroxx
此快照首次捕获于
2025/12/03 02:25
3 个月前
此快照最后确认于
2025/12/03 02:25
3 个月前
查看原文

题意

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

思考

先考虑枚举 aa，因为 c≥1c \ge 1，所以 amod  b≠0a \mod b \neq 0，即 bb 不是 aa 的因数。
所以每个 aa 对应的个数为 a−(aa - ( a 的因数个数 ) )。
两部分分开计算，第一部分的和是 n(n+1)2\frac{n(n+1)}{2} 应该没人不会吧，
重点在第二部分，
相当于求 b∣a,1≤a,b≤nb | a , 1 \le a , b \le n 的 (a,b)(a,b) 个数
也就是对于每个 bb 求其倍数个数，即
∑i=1n⌊ni⌋\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor
答案为 n(n+1)2−∑i=1n⌊ni⌋\frac{n(n+1)}{2}-\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor
于是变成了数论分块的模板，时间复杂度 O(n)O(\sqrt n)。

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

用于求 ∑i=1nf(i)g(⌊ni⌋)\sum_{i=1}^{n}f(i)g(\lfloor\frac{n}{i}\rfloor) 的 O(n)O(\sqrt n) 算法
i≤ni\le \sqrt n 的直接暴力，之后每次找到一个 ⌊ni⌋\lfloor\frac{n}{i}\rfloor 相等的区间一起计算
具体求区间的方法：每次根据上一个区间确定 ll，则 r=⌊n⌊nl⌋⌋r = \lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor 证明：
设 ⌊nl⌋=k\lfloor\frac{n}{l}\rfloor = k
则对于区间中的任意一个数 jj， j×k≤nj \times k \le n
故 j≤⌊nk⌋=⌊n⌊nl⌋⌋=r j\le \lfloor\frac{n}{k}\rfloor = \lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor =r

代码

CPP
#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);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...