답안 #9539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9539 2014-09-28T07:06:55 Z corea Xtreme gcd sum (kriii2_X) C++14
1 / 4
4000 ms 123560 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 32612 KB Output is correct
2 Correct 4 ms 32612 KB Output is correct
3 Correct 4 ms 32612 KB Output is correct
4 Correct 4 ms 32612 KB Output is correct
5 Correct 0 ms 32612 KB Output is correct
6 Correct 4 ms 32612 KB Output is correct
7 Correct 4 ms 32612 KB Output is correct
8 Correct 0 ms 32612 KB Output is correct
9 Correct 0 ms 32612 KB Output is correct
10 Correct 8 ms 32612 KB Output is correct
11 Correct 2588 ms 122636 KB Output is correct
12 Correct 2588 ms 123164 KB Output is correct
13 Correct 2580 ms 123032 KB Output is correct
14 Correct 2504 ms 120524 KB Output is correct
15 Correct 2536 ms 121580 KB Output is correct
16 Correct 184 ms 41456 KB Output is correct
17 Correct 2100 ms 107192 KB Output is correct
18 Correct 2348 ms 115640 KB Output is correct
19 Correct 600 ms 58220 KB Output is correct
20 Correct 1148 ms 76832 KB Output is correct
21 Correct 2612 ms 123560 KB Output is correct
22 Correct 2616 ms 123560 KB Output is correct
23 Correct 2600 ms 123560 KB Output is correct
24 Correct 2580 ms 123560 KB Output is correct
25 Correct 2572 ms 123560 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 32612 KB Output is correct
2 Correct 12 ms 32612 KB Output is correct
3 Correct 4 ms 32612 KB Output is correct
4 Correct 8 ms 32612 KB Output is correct
5 Correct 12 ms 32612 KB Output is correct
6 Correct 8 ms 32612 KB Output is correct
7 Correct 12 ms 32612 KB Output is correct
8 Correct 4 ms 32612 KB Output is correct
9 Correct 8 ms 32612 KB Output is correct
10 Correct 16 ms 32612 KB Output is correct
11 Execution timed out 4000 ms 123556 KB Program timed out
12 Halted 0 ms 0 KB -