首页 > 代码库 > codevs2606 约数和问题
codevs2606 约数和问题
题目描述 Description
Smart最近沉迷于对约数的研究中。
对于一个数X,函数f(X)表示X所有约数的和。例如:f(6)=1+2+3+6=12。对于一个X,Smart可以很快的算出f(X)。现在的问题是,给定两个正整数X,Y(X<Y),Smart希望尽快地算出f(X)+f(X+1)+……+f(Y)的值,你能帮助Smart算出这个值吗?
输入描述 Input Description
输入文件仅一行,两个正整数X和Y(X<Y),表示需要计算f(X)+f(X+1)+……+f(Y)。
输出描述 Output Description
输出只有一行,为f(X)+f(X+1)+……+f(Y)的值。
样例输入 Sample Input
2 4
样例输出 Sample Output
14
数据范围及提示 Data Size & Hint
对于20%的数据有1≤X<Y≤10^5。
对于60%的数据有1≤X<Y≤1*10^7。
对于100%的数据有1≤X<Y≤2*10^9。
正解:分块
解题报告:
据说是一道普及组题,我居然想了这么久,没戏了。
区间[l,r]的约数和之和,直接转端点相减。然后考虑答案肯定是ans=∑[n/i]*i(1<=i<=n); 但我们没有必要for一遍所有的i,可以把[n/i]相等的区间一起处理(分块处理),直接对这个区间求和就可以了。
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector>10 #include <queue>11 #include <map>12 #include <set>13 using namespace std;14 typedef long long LL;15 //ans=∑[n/i]*i(1<=i<=n); 按[n/i]分块处理16 17 inline int getint()18 {19 int w=0,q=0; char c=getchar();20 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 21 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;22 }23 24 inline LL solve(LL n){25 if(n==0 || n==1) return n;26 LL left=1,right; LL ans=0;27 while(left<=n) {28 right=n/(n/left);//确定[n/i]为同一值的右端点29 ans+=(n/left)*(left+right)*(right-left+1)/2;30 left=right+1;31 }32 return ans;33 }34 35 inline void work(){36 LL x,y; x=getint(); y=getint();37 printf("%lld",solve(y)-solve(x-1));38 }39 40 int main()41 {42 work();43 return 0;44 }
codevs2606 约数和问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。