题目背景
数学题,无背景
题目描述
给出正整数 n,k计算k取模1~n的和
数学好题,代码短小精悍
暴力能60,
之后考虑优化。
如果你学过一点点数学,那么你就知道
k%i=k-[k/i]*i;
而且不难发现,[k/i]必定是连续的,且在一定的i的范围内这个值是不变的,类似于一个阶梯函数,而我们阔以通过k/[k/i]来算出这个东西的右边界(为什么自己用纸算一下就知道了)
然后就用阔以把这个东西分块了,等差数列求和
一个数的因子期望是根号这个数
所以这个题的期望复杂度是根号N
1e9轻松跑过
上我可爱的代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#define int long long
using namespace std;
int n,k;
int ans;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
main(){
n=read();k=read();
ans=n*k;
int r=2;
for(int i=1;i<=n;i=r+1){
if(k/i!=0) {
r=k/(k/i);
if(r>n) r=n;//注意考虑一下这里,因为没给n和k的大小,一开始我没考虑少了50分嘤嘤嘤
ans-=(k/i)*(r-i+1)*(i+r)/2;
}
else if(k<i) break;
}
printf("%lld",ans);
return 0;
}