BZOJ 1257-余数之和

[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;
}