1257: [CQOI2007]余数之和sum

Time Limit: 5 Sec  Memory Limit: 162 MB

Submit: 2001  Solved: 928

[ ][ ]

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

10               

if x>y 

then max:=x 

else max:=y;

11          

end;

12 

13 

function find1(x,y:longint):longint;

14          

var l,r,i,j:longint;

15          

begin

16               l:=

1;r:=x;

17               

while l<r 

do

18                     

begin

19                          

if (x 

div ((l+r) 

div 

2))>y 

then l:=(l+r) 

div 

2+

1 

else r:=(l+r) 

div 

2;

20 

21                          i:=

1;

22                     

end;

23               find1:=r;

24          

end;

25 

function find2(x,y:longint):longint;

26          

var l,r,i,j:longint;

27          

begin

28               l:=

1;r:=x;

29               

while l<(r-

1) 

do

30                     

begin

31                          

if (x 

div ((l+r) 

div 

2))>=y 

then l:=(l+r) 

div 

2 

else r:=(l+r) 

div 

2-

1;

32 

33                          i:=

1;

34                     

end;

35               

if (x 

div r)=y 

then exit(r) 

else exit(l);

36          

end;

37 

38 

function ca(x,z:longint):int64;

39          

var i,j,a1,a2:longint;

40          y:int64;

41          

begin

42               y:=

0;

43               

for i:=

1 

to trunc(sqrt(x)) 

do

44                   

begin

45                        

if i>z 

then break;

46                        a1:=min(find2(x,i),z);

47                        a2:=max(find1(x,i),trunc(sqrt(x))+

1);

48                        y:=y+(x 

div i)*i;

49                        

if a2<=a1 

then y:=y+int64((int64(a1+a2)*int64(a1-a2+

1) 

div 

2)*i);

50                   

end;

51               exit(y);

52          

end;

53 

begin

54            

begin

55                 readln(m,n);

56                 writeln(int64(n)*int64(m)-ca(n,min(n,m)));

57            

end;

58 

end.

59