洛谷P2261 [CQOI2007]余数求和

传送门

题目背景
数学题，无背景

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