1257: [CQOI2007]余数之和sum
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 1908 Solved: 887
[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
根据x%i=x-[x/i]*i
转化为求[x/i]的总和，迭代转化为等差数列求和
迭代法代码背了好多次了，还是忘了。。。。放在代码模板里吧
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive
************************************************/
/////////////////////////////////////////////////
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
/////////////////////////////////////////////////
int n,k;
/////////////////////////////////////////////////
/////////////////////////////////////////////////
void input()
{
scanf("%d%d",&n,&k);
}
void solve()
{
///////////////////init///////////////////
LL ans=0;
int r;
////////////////calculate////////////////
if(n>k)
{
ans=(LL)(n-k)*k;
n=k;
}
for(int i=1;i<=n;i=r+1)
{
int t=k/i;r=k/t;
if(r>=n)r=n;
ans+=(LL)(r-i+1)*k-(LL)(r-i+1)*(i+r)/2*t;
}
/////////////////output/////////////////
printf("%lld\n",ans);
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("std.in","r",stdin); freopen("std.out","w",stdout);
#endif
input();
solve();
#ifdef _TEST
for(;;);
#endif
return 0;
}