洛谷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;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-20 07:39
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-15 18:06
华南理工大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议