P2261 [CQOI二零零五]余数求和

主题材料背景

数学题,无背景

题目陈说

付出正整数n和k,计算G=k mod 1 + k mod 2 + k mod 3 + … + k mod
n的值,个中k mod i代表k除以i的余数。举个例子G=5 mod 1 + 5 mod 2 + 5 mod 3 +
5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29

输入输出格式

输入格式:

多个整数n k

出口格式:

答案

输入输出样例

输入样例#1:

10 5

输出样例#1:

29

说明

30%: n,k <= 1000

60%: n,k <= 10^6

100% n,k <= 10^9

找规律并证实能够:

图片 1$

也等于说几个相邻的自然数,若被k除的商一样,则被k取模后的多个数相差-q。

就此,只要搜索八个距离[i,j],使得k/i=k/=…=k/j,就可以用等差数列公式求出k
mod i + k mod + … + k mod j。

以此职务就是:解方程[k/x]=p。

能够随意赢得px<=k<x,而作者辈只关心px<=k,即x<=k/p,得出x=[k/p]。

对于每三个i,令p=[k/i],
q=k mod i,j=min。

基于等差数列公式获得k mod
i + … + k mod j = q*-*/2*p。

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define lli long long int using namespace std;void read(lli &n){char c='+';lli x=0;bool flag=0;while(c<'0'||c>'9'){c=getchar();ifflag=1;}while(c>='0'&&c<='9')x=x*10+,c=getchar();flag==1?n=-x:n=x;}lli ans=0,p,q,n,k;int main(){    read;read;    for(lli i=1; i<=n; i++) {        p=k/i;q=k%i;        lli j=p?k/p:n;        ifj=n;        ans+=q*-*/2*p;        i=j;    }    printf("%lld",ans);return 0;}

  

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图