首页 > 代码库 > hunnu11546:Sum of f(x)
hunnu11546:Sum of f(x)
Problem description |
令f(x)为x的全部约数之和,x的约数即能够被x整除的数。如f(24)=1+2+3+4+6+8+12+24=60),求 f(l) + f(l + 1) + …… + f(r) |
Input |
第一行为一个整数T(T<=100000),表示数据的组数。
|
Output |
对每组数据,输出f(l)+f(l+1)+……+f(r) 的和 |
Sample Input |
2 3 5 10 20 |
Sample Output |
17 270 |
Problem Source |
HUNNU Contest |
開始用这样的方法来求
for(i = 3; i<=200000; i++) { a[i] = 1+i; for(j = 2; j*j<=i; j++) { if(i%j==0) { a[i]+=j; if(i/j!=j) a[i]+=(i/j); } } }
超时。改成
for(i = 1; i<=200000; i++) { for(j = 1; i*j<=200000; j++) { a[i*j]+=i; } }
才AC
开了一个变量去级数,发现上面的运算了5千多W次
以下的才两百多W次
看来区别还是蛮大的
#include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <math.h> #include <bitset> #include <algorithm> #include <climits> #include <time.h> using namespace std; #define LS 2*i #define RS 2*i+1 #define UP(i,x,y) for(i=x;i<=y;i++) #define DOWN(i,x,y) for(i=x;i>=y;i--) #define MEM(a,x) memset(a,x,sizeof(a)) #define W(a) while(a) #define gcd(a,b) __gcd(a,b) #define LL long long #define N 200005 #define MOD 1000000007 #define INF 0x3f3f3f3f #define EXP 1e-8 LL a[N]; LL sum[N]; void init() { LL i,j,k; MEM(a,0); MEM(sum,0); for(i = 1; i<=200000; i++) { for(j = 1; i*j<=200000; j++) { a[i*j]+=i; } } for(i = 1; i<=200000; i++) sum[i] = sum[i-1]+a[i]; } int main() { LL i,j,k; int l,r; init(); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&l,&r); printf("%I64d\n",sum[r]-sum[l-1]); } return 0; }
hunnu11546:Sum of f(x)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。