洛谷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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 14:23
steelhead:你回的有问题,让人感觉你就是来学习的
点赞 评论 收藏
分享
求offer的大角牛:不吃香菜
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:13
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务