usqwedf

T=Sigma(i=1,n)K mod i
=Sigma(i=1,n)K-[K/i]*i
=Sigma(i=1,n)K-Sigma(i=1,n)[K/i]*i
=n*K-Sigma(i=1,n)[K/i]*i

令 P=Sigma(i=1,n)[K/i]*i
接下来在 O(Sqrt(n)) 的复杂度求出 P

举个例子

30 14

30=1*30+0
30=2*15+0
30=3*10+0
30=4*7+2
30=5*6+0
30=6*5+0
30=7*4+2
30=8*3+6
30=9*3+3
30=10*3+0
30=11*2+8
30=12*2+6
30=13*2+4
30=14*2+2

观察到
30=8*3+6
30=9*3+3
30=10*3+0
余数成等差数列而[K/i]相同可以快速求和

简要证明
k-[k/i]*i
[k/i]*i
[k/i]*(i+1)
所以增量为[k/i] 成等差数列

[k/[k/i]] 表示 [k/i] 最远的拓展 最远的值 (i)
[最大可以增到的量 如果超过这个 那么 [k/i] 将会变化]
[实际上可以采用不等式证明]

例如在所举的例子中 30 Div 8 这是第一个值
而 30 Div (30 Div 8) = 10 是 [k Div i] 相同的最后一个

 

 

Var
  n,k,T,Right,i:Int64;
   
Begin
  Readln(n,k);
  T:=n*k;
  i:=1;
  While i<=n do begin
      if k Div i=0 then Break;
      Right:=k Div (k Div i);
      if Right>n then Right:=n;
      T:=T-(i+Right)*(Right-i+1)*(k Div i) Div 2;
      i:=Right+1;
  End;
  writeln(T);
End.