oj.uz

답안 #9577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9577 2014-09-28T07:22:51 Z veckal Xtreme gcd sum (kriii2_X) C++14
0 / 4
 92 ms 8976 KB 
#include<stdio.h>
const int MOD = 1000000000 + 7;

int n, a[10000], b[10000];
long long num[1000000];

int main() {
	scanf("%d", &n);
	for (int i=0;i<n; ++i)
		scanf("%d%d", a+i, b+i);
	long long ans = 0;
	for (int i=1000000; i>0; --i) {
		num[i] = 1;
		for (int j=0; j<n; ++j) {
			num[i] *= b[j]/i - (a[j]-1)/i;
			num[i] %= MOD;
		}
		for (int j=i+i; j<=1000000; j+=i) {
			num[i] -= num[j];
			if (num[i] < 0) num[i] += MOD;
		}
		ans += i * num[i];
		ans %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 8976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -