区间因子

给定n个询问，需要输出[L,R]范围内每个数的因子个数之和。

输入描述:

第一行一个整数n,表示询问数量。
接下来n行，每行两个整数L和R。

输出描述:

对于每个询问，输出相应的结果。

示例1
输入

2
10 55
33 101

输出

208
365

qujianyinzi.cppview raw

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 2000010;
int st[N+10];
int sum[N+10];

int n;

int main(){
    for(int i=1;i<=N;i++) sum[i] = 1;
    for(int i=2;i<=N;i++){ //O(nloglogN)
        if(!st[i]){
            for(int j=i+i;j<=N;j+=i) st[j] =1;
            for(int j=i;j<=N;j+=i){
                int t = j, c= 0;
                while(t%i==0){
                    c++, t/=i;
                }
                sum[j]*=(c+1);
            }
        }
    }

    for(int i=1;i<=N;i++)
        sum[i] += sum[i-1];

    scanf("%d", &n);
    while(n--){
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%d\n", sum[R] - sum[L-1]);
    }
    return 0;
}