首页 > 代码库 > [原博客] BZOJ 1257 [CQOI2007] 余数之和

[原博客] BZOJ 1257 [CQOI2007] 余数之和

题目链接
题意:
  给定n,k,求 ∑(k mod i) {1<=i<=n} 其中 n,k<=10^9
  即 k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。


我们先来看商之和。
  给定n,k,求∑(k/i) {1<=i<=n} 其中/为整除。


可以得到一个引理,k/i值的个数不超过2*√k
证明:k整除小于√k的数,都会有一个不同的结果;k整除大于√k的数,结果肯定小于√k,所以最多也只能有√k种结果。

于是我们可以枚举结果的取值累加。是O(√k)级别的。

代码可以这样写:

LL sum(LL n,LL k){ //calc sigma(k/i) 1<=i<=n    LL sum = 0;    for(LL i = 1 ; i <= n ; i ++ ){        LL a = k / i ; LL b = k / a ;        b = min(b,n) ;        sum += a * (b-i+1) ;    }    return sum;}
View Code

其中ak/i的值,b是最大得到k/i这个值的数,b-i+1为取得同一个值的区间长度。

然后来看余数之和:
我们知道 a mod b == a - a/b*b (整除)。
  于是 ∑(k mod i) {1<=i<=n}就可以写成n*k-∑k/i*i {1<=i<=n}对于k/i值相同的一段,后面那一项是一个等差数列,求和就好了。

/**************************************************************    Problem: 1257    User: zrts    Language: C++    Result: Accepted    Time:8 ms    Memory:1272 kb****************************************************************/ #include<iostream>#include<cstdio>#include<algorithm>#include<cstring> //by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);LL n,k;int main(){    #ifdef LOCAL    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    #endif    scanf("%lld%lld",&n,&k);    LL ans=n*k;    LL sub=0;    for(int i=1;i<=n&&i<=k;i++){        LL a=k/i;LL b=k/a;        b=min(b,n);        sub+=a*(i+b)*(b-i+1)/2;        i=b;    }    printf("%lld\n",ans-sub);    return 0;}
View Code

另有一道题:切巧克力。在SegmentFault上有人提问,链接。我的回答就是用了与这个类似的方法。

[原博客] BZOJ 1257 [CQOI2007] 余数之和