1257: [CQOI2007]余数之和sum
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 2001 Solved: 928
[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
Source
题解：第一反应很明显——直接枚举，但是肯定TLE，于是我们发现X mod Y=X-[X/Y]，这样子X的累计不难，于是乎关键问题转化为了[X/Y]的累计，当Y>=X时不用说啥，关键是Y<X时，假如O(N)的话，那么还是白搞了。。。所以可以考虑缩减到trunc(sqrt(n))级别——对于这一范围内的数直接算，对于商为[N/I]的只需要用二分确定其范围，然后直接累加，别的没了（Ps：1.注意开int64 2.注意考虑N<K的情况，设一个门楣 3.注意在商运算过程中考虑拍掉重复值，我为此WA了一次）
1 var
2
3 i,j,k,l,m,n:longint;
4 function min(x,y:longint):LONGINT;
5 BEGIN
6 IF X<Y THEN MIN:=X ELSE MIN:=Y;
7 end;
8 function max(x,y:longint):longint;
9 begin
if x>y then max:=x else max:=y;
end;
function find1(x,y:longint):longint;
var l,r,i,j:longint;
begin
l:=;r:=x;
while l<r do
begin
if (x div ((l+r) div ))>y then l:=(l+r) div + else r:=(l+r) div ;
i:=;
end;
find1:=r;
end;
function find2(x,y:longint):longint;
var l,r,i,j:longint;
begin
l:=;r:=x;
while l<(r-) do
begin
if (x div ((l+r) div ))>=y then l:=(l+r) div else r:=(l+r) div -;
i:=;
end;
if (x div r)=y then exit(r) else exit(l);
end;
function ca(x,z:longint):int64;
var i,j,a1,a2:longint;
y:int64;
begin
y:=;
for i:= to trunc(sqrt(x)) do
begin
if i>z then break;
a1:=min(find2(x,i),z);
a2:=max(find1(x,i),trunc(sqrt(x))+);
y:=y+(x div i)*i;
if a2<=a1 then y:=y+int64((int64(a1+a2)*int64(a1-a2+) div )*i);
end;
exit(y);
end;
begin
begin
readln(m,n);
writeln(int64(n)*int64(m)-ca(n,min(n,m)));
end;
end.