QueryTheoryI

NC206675. QueryTheoryI

描述

XiaoYang is building a big system, which uses the pattern of Command Query Responsibility Segregation.

This system holds an array of numbers $\lbrace a_i \rbrace$ of length n, where $a_i = i$ for all $i \in [1, n]$ . And it is designed for a function f(L, R).

$f(L, R) = \sum_{i=L}^R \sum_{j|i} j$

You are developing this system with XiaoYang. Now, Q queries are here for the sequence with $n = 10^6$ . Each query contains two number L, R. You should respond to these queries with the result of that function.

输入描述

The input starts with one line, containing integers $Q ~ (1 \leq Q \leq 10^5)$ .

Then follow Q lines, each containing integers $L, R ~ (1 \leq L \leq R \leq 10^6)$ denoting the query parameters.

输出描述

For each query, output the answer in one line.

示例1

输入:

1
1 5

输出:

说明:

For the first query, f(1, 5) = 1 + 3 + 4 + 7 + 6 = 21.

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 126ms, 内存消耗: 9448K, 提交时间: 2020-06-13 18:16:15

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ar[1000005];

int main(){
	for(int i=1;i<=1000000;i++){
		for(int j=i;j<=1000000;j+=i) ar[j]+=i;
	}
	for(int i=2;i<=1000000;i++) ar[i]+=ar[i-1];
	int n;
	scanf("%d",&n);
	while(n--){
		int l,r;
		scanf("%d %d",&l,&r);
		printf("%lld\n",ar[r]-ar[l-1]);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 85ms, 内存消耗: 9452K, 提交时间: 2020-06-15 09:27:18

#include<stdio.h>
#define bb 1000007
long long int a,b,i,I,sum,A[bb],K;
int main()
{
	for(i=1;i<=bb;i++)
		for(I=i,sum=0;I<=bb;I=I+i)
			A[I]=A[I]+i;
	for(i=1;i<=bb;i++)A[i]=A[i-1]+A[i];
	scanf("%lld",&K);
	while(K--)
		scanf("%lld%lld",&a,&b),
		printf("%lld\n",A[b]-A[a-1]);
}