bzoj 1257 [CQOI2007] 余數之和 sum 題解

【題目】

Description

給出正整數n和k，計算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余數。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

輸入僅一行，包含兩個整數n, k。

Output

輸出僅一行，即j(n, k)。

Sample Input

Sample Output

HINT

50%的數據滿足：1<=n, k<=1000 100%的數據滿足：1<=n ,k<=10^9

【分析】這道題我研究了半天，最後還是CLJ大神的題解給了我一點啟發。然後我又深入研究，總算A了。首先，當N>K的時候直接加上(N-K)*K就行了。然後我們來研究Σ(K MOD I)(1<=i<=K)。K MOD I=K-TRUNC(K/I)*I.而且CLJ大神說，K/I最多只有SQRT(N)個。（其實打個表就知道了）那麼我們把K/I相等的分在一組裡進行操作，而且可以發現，如果一坨數字在同一組，他們的余數構成等差數列。每次用二分去找一組的尾邊界。

【代碼】

/**************************************************************
    Problem: 1257
    User: jiangshibiao
    Language: C++
    Result: Accepted
    Time:108 ms
    Memory:804 kb
****************************************************************/
 
#include
#include
using namespace std;
typedef long long ll;
ll n,k,now,chu,last,ans;
ll erfen(ll l,ll r)
{
  if (l==r) return l;
  ll mid=(l+r)/2+1;
  if (ll(k/mid)==chu) return erfen(mid,r);
  return erfen(l,mid-1);
}
int main()
{
  scanf(%lld%lld,&n,&k);
  if (n>k) ans+=(n-k)*k;
  if (n>k-1) n=k-1;
  now=1;
  while (now<=n)
  {
    chu=ll(k/now);
    last=erfen(now,n);
    ans+=(2*k-chu*(now+last))*(last-now+1)/2;
    now=last+1;
  }
  printf(%lld,ans);
  return 0;
}