样例已过,0pts
对于k<=3的暴力算
对于k>3的:
将问题转化为ans=n∗k−∑i=1kk/i
所以我们来计算∑i=1kk/i
设s=k(向下取整)
n在1~s-1区间内的时候暴力减去
n在s~k区间内的时候:
会有连续的几个数值都是相等的,这些相等的值<=s
我们枚举相等的值,然后计算出每次有这些值的位置l和r,然后用等差数列公式算出有这些相等的值的位置的编号之和,乘上这个值,作为这一段的k/i的和。
代码如下:
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
ll ans,n,k,s;
cin>>n>>k;
s=sqrt(k);
if(k<=3)
{
for(int i=1;i<=min(n,k);i++) ans+=k%i;
if(k<n) ans+=(n-k)*k;
}
else
{
ans=n*k;
for(int i=1;i<s;i++) ans-=(k/i*i);
for(int i=1;i<=s;i++)
{
int r=k/i;
int l=k/(i+1)+1;
ans-=((r-l+1)*i*(l+r)/2);
}
}
cout<<ans;
}