P2261 [CQOI2007]余数求和
2018-06-17 22:13:43来源:未知 阅读 ()
题目背景
数学题,无背景
题目描述
给出正整数n和k,计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。例如G(10, 5)=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
输出格式:
答案
输入输出样例
10 5
29
说明
30%: n,k <= 1000
60%: n,k <= 10^6
100% n,k <= 10^9
找规律并证明可知:
$
也就是说两个相邻的自然数,若被k除的商相同,则被k取模后的两个数相差-q。
所以,只要找出一个区间[i,j],使得k/i=k/(i+1)=...=k/j,即可用等差数列公式求出k mod i + k mod (i+1) + ... + k mod j。
这个任务就是:解方程[k/x]=p。
可以轻易得到px<=k<(p+1)x,而我们只关注px<=k,即x<=k/p,得出x=[k/p]。
对于每一个i,令p=[k/i], q=k mod i,j=min(n,k/p)。
根据等差数列公式得到k mod i + ... + k mod j = q*(j-i+1)-(j-i+1)*(j-i)/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();if(c=='-')flag=1;} while(c>='0'&&c<='9') x=x*10+(c-48),c=getchar(); flag==1?n=-x:n=x; } lli ans=0,p,q,n,k; int main() { read(n);read(k); for(lli i=1; i<=n; i++) { p=k/i;q=k%i; lli j=p?k/p:n; if(j>n) j=n; ans+=q*(j-i+1)-(j-i+1)*(j-i)/2*p; i=j; } printf("%lld",ans); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:P1421 小玉买文具
下一篇:历年NOIP中的搜索题
- 1007. 计算余数 2018-06-18
- 十进制转十六进制 2018-06-18
- 【DTOJ】2703:两个数的余数和商 2018-06-17
- 【DTOJ】2702:余数 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash