Submission #9539

#	Time	Username	Problem	Language	Result	Execution time	Memory
9539		corea	Xtreme gcd sum (kriii2_X)	C++14	1 / 4	4000 ms	123560 KiB

X

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

long long MOD = 1000 * 1000 * 1000 + 7;
vector<int> divisor[ 1000003 ];

int N;

long long A[ 10003 ];
long long B[ 10003 ];
long long S[ 1000003 ];

void init() {
	int m = *max_element( B + 1, B + N + 1 );

	int s = 0;
	for( int i = 1; i <= m; i ++ ) {
		for( int j = i + i; j <= m; j += i ) {
			divisor[ j ].push_back( i );
			s ++;
		}
	}
}

int main() {
	scanf( "%d", &N );

	for( int i = 1; i <= N; i ++ ) {
		scanf( "%lld %lld", &A[ i ], &B[ i ] );
	}
	init();

	long long res = 0;
	for( long long i = (*max_element(B + 1, B + N + 1)); i >= 1; i -- ) {
		long long s = 1;

		for( int j = 1; j <= N; j ++ ) {
			s *= (B[ j ] / i - (A[ j ] - 1) / i );
			s %= MOD;
		}

		S[ i ] += s;
		s %= MOD;
		S[ i ] += MOD;
		s %= MOD;

		for( auto &v : divisor[ i ] ) {
			S[ v ] -= S[ i ];
			S[ v ] %= MOD;
			S[ v ] += MOD;
			S[ v ] %= MOD;
		}

		// printf( "%d %d\n", i, S[ i ] );
		res += (S[ i ] * i);
		res %= MOD;
	}

	printf( "%lld\n", res );
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 3