首页 > 代码库 > [原博客] 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;}
其中a
是k/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;}
另有一道题:切巧克力。在SegmentFault上有人提问,链接。我的回答就是用了与这个类似的方法。
[原博客] BZOJ 1257 [CQOI2007] 余数之和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。