传送门

题目背景
数学题,无背景

题目描述
给出正整数 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;
}