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。

1<=n ,k<=10^9

Output

输出仅一行，即j(n, k)。

 

题解：

一眼整除分块.

根据整除分块的性质，会有连续一段区间对应的整出结果是相同的，那么这段区间的于是也应该是依次加一的.

用整除分块和等差数列求和公式搞一搞即可.

Code:

#include
     
      #define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 1000000 #define ll long long using namespace std;int main(){    // setIO("input");     ll n,k,ans=0;       scanf("%lld%lld",&n,&k);     if(k>=n){        for(ll i=1,j;i<=n;i=j+1){            j=k/(k/i);                        ll a=k%i,b=k%min(n,j),len=min(n,j)-i+1;             ans+=((a+b)*len);                     }        printf("%lld",(ans>>1));     }else {        for(ll i=1,j;i<=k;i=j+1){            j=k/(k/i);                        ll a=k%i,b=k%min(k,j),len=min(k,j)-i+1;             ans+=(ll)((a+b)*len);         }         printf("%lld",(ans>>1)+(n-k)*k);    }    return 0; }