Sum Of Gcd

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=4676

Description

Given you a sequence of number a1, a2, ..., an, which is a permutation of 1...n.

You need to answer some queries, each with the following format:

Give you two numbers L, R, you should calculate sum of gcd(a[i], a[j]) for every L <= i < j <= R.

Input

First line contains a number T(T <= 10),denote the number of test cases.

Then follow T test cases.

For each test cases,the first line contains a number n(1<=n<= 20000).

The second line contains n number a1,a2,...,an.

The third line contains a number Q(1<=Q<=20000) denoting the number of queries.

Then Q lines follows,each lines contains two integer L,R(1<=L<=R<=n),denote a query.

Output

For each case, first you should print "Case #x:", where x indicates the case number between 1 and T.

Then for each query print the answer in one line.

Sample Input

1

5

3 2 5 4 1

3

1 5

2 4

3 3

Sample Output

Case #1:

11

4

0

Hint

题意

给你n个数，然后Q次询问，每次问你l,r区间的两两之间的GCD和是多少

题解：

莫队+反演，直接暴力莽就好了……

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e4 + 15;

int unit , a[maxn] , N , M , cnt[maxn];

long long ans[maxn] , phi[maxn];

vector < int > factor[maxn];

struct Query{

    int l , r  , idx;

	friend bool operator < (const Query & a , const Query & b){

		int x1 = a.l / unit , x2 = b.l / unit;

		if( x1 != x2 ) return x1 < x2;

		return a.r < b.r;

	}

}Q[maxn];

void Init(){

	for(int i = 1 ; i < maxn ; ++ i)

		for(int j = i ; j < maxn ; j += i)

			factor[j].push_back( i );

	phi[1] = 1;

	for(int i = 2 ; i < maxn ; ++ i)

		if( !phi[i] )

			for(int j = i ; j < maxn ; j += i){

				if( !phi[j] ) phi[j] = j;

				phi[j] = phi[j] *  ( i - 1 ) / i;

			}

}

long long add( int x ){

	long long res = 0;

	for( auto d : factor[x] ) res += cnt[d] * phi[d];

	for( auto d : factor[x] ) cnt[d] ++ ;

	return res;

}

long long del( int x ){

	long long res = 0;

	for( auto d : factor[x] ) cnt[d] -- ;

	for( auto d : factor[x] ) res += cnt[d] * phi[d];

	return -res;

}

void solve(){

	memset( cnt , 0 , sizeof( cnt ) );

	int l = 1 , r = 0;

	long long cur = 0;

	for(int i = 1 ; i <= M ; ++ i){

		while( l < Q[i].l ) cur += del( a[l++] );

		while( l > Q[i].l ) cur += add( a[--l] );

		while( r < Q[i].r ) cur += add( a[++r] );

		while( r > Q[i].r ) cur += del( a[r--] );

		ans[Q[i].idx] = cur;

	}

}

int main( int argc , char * argv[] ){

	Init();

	int Case , cas = 0;

	scanf("%d",&Case);

	while(Case--){

		scanf("%d",&N);

		for(int i = 1 ; i <= N ; ++ i) scanf("%d" , a + i);

		scanf("%d",&M);

		for(int i = 1 ; i <= M ; ++ i){

			Q[i].idx = i;

			scanf("%d%d",&Q[i].l,&Q[i].r);

		}

		unit = sqrt( N );

		sort( Q + 1 , Q + M + 1 );

		solve();

		printf("Case #%d:\n" , ++ cas);

		for(int i = 1 ; i <= M ; ++ i) printf("%lld\n" , ans[i]);

	}

	return 0;

}

巴特西

hdu 4676 Sum Of Gcd 莫队+phi反演