bzoj 1257 [CQOI2007] 余数之和 sum 例题
bzoj 1257 [CQOI2007] 余数之和 sum 题解
Submit: 1344 Solved: 615
[Submit][Status]
转载请注明:http://blog.csdn.net/jiangshibiao/article/details/21649423
【题目】
1257: [CQOI2007]余数之和sum
Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 1344 Solved: 615
[Submit][Status]
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
【分析】这道题我研究了半天,最后还是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<cstdio> #include<cmath> 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; }