题目背景
数学题，无背景
题目描述
给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29
输入输出格式
输入格式：
两个整数n k
输出格式：
答案
输入输出样例
说明
30%: n,k <= 1000
60%: n,k <= 10^6
100% n,k <= 10^9
Solution:
本题$zyys$的数论分块。
类似于$Ahoi$约数研究的思路。
首先，对取模式子化简得：$k;mod;i=k-i imeslfloor{k/i} floor$。
所以最后的$ans=sumlimits_{i=1}^{n}{(k-i imeslfloor{k/i} floor)}=n imes k-sumlimits_{i=1}^{n}{i imeslfloor{k/i} floor}$
对于$i imeslfloor{k/i} floor$中，$lfloor{k/i} floor$有许多是相同的，假设$x=lfloor{k/i} floor$（$i$为第一次出现$x$值的下标），则$i_{max}=lfloor{k/x} floor$，从$i$到$i_{max}$共有$i_{max}-i+1$个$x$。
注意到$i imeslfloor{k/i} floor$中还有系数$i$，而$i$到$i_{max}$是递增的（每次加$1$），所以是一个公差为$x$的等差序列，直接套上等差数列求和公式即可。
因为$ileq n$且$lfloor{k/i} floor$可能为$0$，所以记得判断边界。
由于$lfloor{k/i} floor$的值最多有$2 imessqrt{n}$个，所以时间复杂度为$O(sqrt{n})$。
代码：
#include<bits/stdc++.h> #define il inline #define ll long long #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)>(b)?(b):(a)) using namespace std; ll ans=0,n,k; int main(){ ios::sync_with_stdio(0); cin>>n>>k; int p; ans=n*k; for(ll i=1;i<=n;i=p+1){ p=(k/i?Min(k/(k/i),n):n); ans-=(k/i)*(i+p)*(p-i+1)/2; } cout<<ans; return 0; }