[mathjax]
题目：
给定正整数 \(n\)和 \(k\)，计算\((k\mod 1)+(k\mod 2)+…+(k\mod n)\)的值.\(1<=n,k<=10^9\).
思路:
直接暴力求果断TLE了.所以需要适当转化,降低时间复杂度.
整个式子可以转化为\( n*k-\sum_{i=1}^n\lfloor k/i\rfloor *i\) .
对于任意整数 \( x\in [1,k]\),设 \(g(x)=\lfloor k/\lfloor k/x\rfloor \rfloor\),有\(g(x)>=\lfloor k/(k/x)\rfloor =x\), 故\( \lfloor k/g(x)\rfloor <=\lfloor k/x \rfloor\).
另有,\(\lfloor k/g(x) \rfloor >=\lfloor k/(k/\lfloor k/x \rfloor ) \rfloor = \lfloor k/k* \lfloor k/x \rfloor \rfloor = \lfloor k/x \rfloor \) ,故\( \lfloor k/g(x) \rfloor =\lfloor k/x \rfloor \).
所以,\( \forall i \in [x,\lfloor k/ \lfloor k/x \rfloor \rfloor ],\lfloor k/i \rfloor \) 的值都相等.
\( \forall i \in [1,k] ,\lfloor k/i \rfloor \) 至多只有\(2*\sqrt{k}\)个不同的值.当\( i<= \sqrt{k}\) 时, \( \lfloor k/i \rfloor \)至多只有 \( \sqrt{k} \)个不同的值,而当\( i> \sqrt{k} \)时, \( \lfloor k/i \rfloor < \sqrt{k} \) ,故\( \lfloor k/i \rfloor \)也至多只有 \( \sqrt{k} \)个不同的值.
综上所述,对于 \( i \in [1,k] \) ,\( \lfloor k/i \rfloor \)由不超过\( 2*\sqrt{k} \)段组成,每一段 \( i \in [x, \lfloor k/ \lfloor k/x \rfloor \rfloor] \)中 \(\lfloor k/i \rfloor\)的值都等于\(\lfloor k/x \rfloor\). \( i*\lfloor k/i \rfloor\) 在段中,就是公差为\( \lfloor k/x \rfloor \)的等差数列.
整个算法时间复杂度为O(\(\sqrt{k}\)).
代码:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
#define MAX_N 2e9
typedef long long ll;
typedef unsigned long long ull;
int main() {
ll n ,k;
cin>>n>>k;
ll ans=n*k;;
for(ll l=1,r;l<=n;l=r+1){
r=k/l? min(k/(k/l),n):n;
ans-=(k/l)*(l+r)*(r-l+1)/2;
}
cout<<ans<<endl;
return 0;
}