（打表+优化）简单的求和 -- zzuli -- 1783

http://acm.zzuli.edu.cn/problem.php?id=1783

1783: 简单的求和

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 170  Solved: 31

SubmitStatusWeb Board

Description

定义f(i)代表i的所有因子和(包括1和i)，给定一个l,r。求f(l)+f(l+1)+...+f(r)。

Input

第一行输入一个t(t<1000)，代表有t组测试数据，接下来每行输入两个数字l,r，(1<=l<=r<=1000000)。

Output

每行输出一个整数，代表和。

Sample Input

2

1 2

3 4

Sample Output

4

11

 

 

感觉这道题的表打的很巧妙， 很好的降低了时间复杂度， 表示膜拜， 反正要我想我是想不到的

 

 

#include<stdio.h>

#include<string.h>

#include<queue>

#include<math.h>

#include<stdlib.h>

#include<algorithm>

using namespace std;

const int N=1e6+;

const int INF=0x3f3f3f3f;

const int MOD=;

typedef long long LL;

LL sum[N];

void Solve()

{

    int i, j;

    sum[] = ; sum[] = ;

    for (i = ; i <= ; i++) ///首先我们肯定要先将1和本身存下来（毕竟我们不会遍历到n哒，会超时）

        sum[i] = i+;

    for (i = ; i*i <= ; i++) ///这个循环是打表的关键，首先我们统计的是因子和，那么不超过sqrt（n）就可以了（这里不这样写不仅会超时，根本没法测试。。。。）

    {

        for (j = i+; i*j <= ; j++)

            sum[i*j] += i+j; ///i是其中一个因子，那么j就是i对应的另一个因子（i*j==n）

        sum[i*i] += i; ///这种情况是i==j的情况，那么只能加上一个i

    }

    for (i = ; i <= ; i++) ///最后将所有的和统计下来，这样当我们要求一个区间的和时可以直接减

        sum[i] = sum[i-]+sum[i];

}

int main ()

{

    int T, l, r;

    Solve();

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d%d", &l, &r);

        printf("%lld\n", sum[r]-sum[l-]);

    }

    return ;

}