Atcoder瞎做

我已经做了2


ARC91D.Reminder,Reminder

题目大意

求有多少对(a,b)满足a,b\leq Na\;mod\;b\geq K

N,K不超过1e5

题解

我们枚举b的值,因为不难注意到固定了b以后,随着a的增加,余数一定是也在增加1的(除非遇到b的倍数,则更新为0

因此,我们认为,对于一个固定的b来说,每当a增加b次,都会对答案产生b-K的贡献

时间复杂度O(n\log n)