【bzoj1257】[CQOI2007]余数之和sum

2015.04.14 17:05 Tue | 2次阅读 | 旧日oi | 固定链接 | 源码

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

5 3

Sample Output

7

HINT

50%的数据满足:1<=n, k<=1000 100%的数据满足:1<=n ,k<=10^9

题解

直接算肯定会tle,我们来找一找规律
我们发现,k/i,只会有根号k个取值,而在每一段取值内,余数都是个等差数列
这是可以证明的,手划了划了就明白了。
所以我们可以分块计算,每次找商相同的一段区间,用求和公式计算即可,时间复杂度O(根号n*logn)

我的程序

#include<iostream>
using namespace std;
#define ll long long
long long n,k;
long long ans=0;
long long tar,temp;
int find(ll l,ll r,ll tar)
{
    ll m;
    while(l<=r)
    {
        m=(l+r)>>1;
        if(k/m>=tar) l=m+1;
        else r=m-1;
    }
    return l-1;
}
int main()
{
    cin>>n>>k;
    ans=n*k;
    long long i=1;
    while(i<=min(k,n))
    {
        tar=k/i;
        temp=find(i,n,tar);
        ans-=tar*((i+temp)*(temp-i+1)/2);
        i=temp+1;
    }
    cout<<ans<<endl;
}```