求助自己yy的一个方法
查看原帖
求助自己yy的一个方法
661575
srz_楼主2022/6/13 19:48

样例已过,0pts

对于k<=3的暴力算
对于k>3的:
将问题转化为ans=nki=1kk/ians=n*k-\sum_{i=1}^{k} k/i
所以我们来计算i=1kk/i\sum_{i=1}^{k} k/i
设s=k\sqrt 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;
}
2022/6/13 19:48
加载中...