AtCoder Beginner Contest 414 补题

AtCoder Beginner Contest 414

根据题意，只需枚举ab即可求出c，同时为了满足abc不同，且在[1,N]的范围内必须有a要大于b，且a不能是b的倍数，那么有对于b它可以贡献的答案是n-(b-1)-n//b即减去小于b的部分和b的倍。这里n-(b-1)可以O(1)计算出，但是n//b需要使用数论分块才能对于给定的数据范围求解

mod=998244353
n=R()
# 首先计算固定的部分
total=((n*(n-1))%mod+(n-1)-(n+2)*(n-1)//2)%mod
# b需要从2开始
l=2
res=0
# 不断求解
while l<=n:
    r=n//(n//l)
    res+=(r-l+1)*(n//l)
    res%=mod
    l=r+1
print((total-res)%mod)