BZOJ 1257

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1257

题意：

给定正整数 $n,k$，求 $(k mod 1) + (k mod 2) + cdots + (k mod n) = sum_{i=1}^{n}(k mod i)$ 的值。

题解：

显然 $k mod i = k - lfloor k/i floor imes i$，因此 $sum_{i=1}^{n}(k mod i) = sum_{i=1}^{n}(k - lfloor k/i floor imes i) = n cdot k - sum_{i=1}^{n}(lfloor k/i floor imes i)$。

对于任意正整数 $x in [1,k]$，设 $g(x) = lfloor frac{k}{lfloor k/x floor} floor$，不难得出 $lfloor k/x floor le k/x Rightarrow frac{k}{lfloor k/x floor} ge frac{k}{k/x} Rightarrow lfloor frac{k}{lfloor k/x floor} floor ge lfloor frac{k}{k/x} floor$，即 $g(x) ge lfloor frac{k}{k/x} floor = lfloor x floor = x$。

又根据 $f(x) = frac{k}{x}$ 是一个单调递减函数，得到

$f(g(x)) le f(x) Rightarrow frac{k}{g(x)} le frac{k}{x} Rightarrow lfloor frac{k}{g(x)} floor le lfloor frac{k}{x} floor$

另一方面，根据 $g(x) le frac{k}{lfloor k/x floor}$ 还能得出

因此，综上可以得出 $lfloor frac{k}{g(x)} floor = lfloor frac{k}{x} floor$；也就是说，对于任意的正整数 $i in [x,g(x)]$，$lfloor frac{k}{i} floor$ 都是相等的。

而与此同时，对于任意的正整数 $i in [1,k]$，$lfloor frac{k}{i} floor$ 的值最多只有 $2 sqrt{k}$ 个，这是因为：

当 $i le sqrt{k}$ 时，$i$ 最多只有 $sqrt{k}$ 个选择，相对应地，$lfloor frac{k}{i} floor$ 也就最多 $sqrt{k}$ 个值；而当 $i > sqrt{k}$ 时，$lfloor frac{k}{i} floor le frac{k}{i} < sqrt{k}$，即 $lfloor frac{k}{i} floor$ 只能取 $1 sim sqrt{k}$ 之间的值。

所以，对于任意的正整数 $i in [1,k]$，$lfloor frac{k}{i} floor$ 的值划分成 $O(sqrt{k})$ 段。每一段上 $i in [x,g(x)]$，$lfloor frac{k}{i} floor$ 的值都等于 $lfloor frac{k}{x} floor$。而在这一段中，$sum_{i=x}^{g(x)}(lfloor k/i floor imes i) = lfloor k/x floor sum_{i=x}^{g(x)}i$，即一个等差数列的求和。因此这个算法时间复杂度为 $O(sqrt{k})$。

AC代码：

/**************************************************************
    Problem: 1257
    User: Dilthey
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:1288 kb
****************************************************************/
 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll n,k,ans;
inline ll g(ll x){return k/(k/x);}
inline ll sum(ll L,ll R){return (L+R)*(R-L+1)/2;}
int main()
{
    while(cin>>n>>k)
    {
        ll ans=n*k;
        n=min(n,k);
        for(ll x=1;x<=n;x=g(x)+1)
        {
            ll y=min(g(x),n);
            ans-=(k/x)*sum(x,y);
        }
        cout<<ans<<endl;
    }
}