1257: [CQOI2007]余数之和sum
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 867 Solved: 393
[Submit][Status][Discuss]
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
k%i=k-k/i*i
所有ans=nk+∑(k/i)*i (k/i的值最多有√k种)
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> #include<cmath> #include<cctype> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define ForD(i,n) for(int i=n;i;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define MAXN (1e9) int n,k; int find(int l,int r,int x) { int ans=l; while (l<=r) { int m=(l+r)>>1; if (k/m==x) ans=m,l=m+1; else r=m-1; } return ans; } int main() { scanf("%d%d",&n,&k); long long p=0; int i=1; while (i<=n) { int lmax=find(i,n,k/i); p+=((long long)(i+lmax)*(lmax-i+1)/2)*(k/i); i=lmax+1; } cout<<(long long)n*k-p<<endl; return 0; }