이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |