BZOJ1257: [CQOI2007]余数之和-布布扣-bubuko.com

BZOJ1257: [CQOI2007]余数之和

Description

给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值其中k mod i表示k除以i的余数。

例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

输入仅一行，包含两个整数n, k。

1<=n ,k<=10^9

Output

输出仅一行，即j(n, k)。

Sample Input

5 3

Sample Output

题解Here!

题目要求：$$Ans=\sum_{i=1}^n(k\%i)$$

首先，我们要知道一个公式：$$a\%b=a-b\times\lfloor\frac{a}{b}\rfloor$$

于是：$$Ans=\sum_{i=1}^n(k-i\times\lfloor\frac{k}{i}\rfloor)$$

$$\Rightarrow Ans=n\times k-\sum_{i=1}^n(i\times\lfloor\frac{k}{i}\rfloor)$$

知道懵逼钨丝反演的应该都会算后面那个——数论分块。

复杂度$O(\sqrt n)$。

记得特判边界。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
long long n,k,ans;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date*w;
}
void work(){
	n=read();k=read();
	ans=n*k;
	for(long long i=1,last=1;i<=n;i=last+1){
		if(k/i!=0)last=min(k/(k/i),n);
		else last=n;
		ans-=1LL*(last-i+1)*(k/i)*(i+last)/2;
	}
	printf("%lld\n",ans);
}
int main(){
	work();
	return 0;
}

BZOJ1257: [CQOI2007]余数之和

原文：https://www.cnblogs.com/Yangrui-Blog/p/9924614.html