oj.uz

답안 #9796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9796 2014-09-28T08:58:58 Z lemonsqueeze Xtreme gcd sum (kriii2_X) C++
0 / 4
 2844 ms 262144 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10000;
const int NUMERIC = 2000000;
typedef long long ll;
 
const ll MM = 1000000007;
const int S = 1000000;

ll pw(ll a, ll b)
{
    ll ans = 1, mul = a;
    while( b > 0 ){
        if( b%2 == 1) ans *= mul;
        mul *= mul; b/=2;
        ans %= MM; mul %= MM;
    }
    return ans;
}
 
ll div(ll a){ return pw(a, MM-2); }

struct data{
	data(){}
	data(int wi,int su,int ad,bool ch):wi(wi), su(su), ad(ad), ch(ch){}
	int wi, su, ad;
	bool ch; // T:a, F:b
	bool operator<(const data &l) const{
		if( wi != l.wi) return wi < l.wi;
		return ch > l.ch;
	}
};

int n;
ll a[N], b[N], d[NUMERIC];
vector<data> list[NUMERIC];
 
int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%lld %lld", &a[i], &b[i]);
		a[i]--;
		int val;
		for(int j=2;j<=S;j++){
			val = a[i] / j;
			list[j].push_back(data(j, val, i, true) );
		}
		for(int j = val-1 ; j >= 0; j--){
			int v = a[i] / (j+1) +1;
			list[v].push_back(data(v, j, i, true) );
		}
		for(int j=2;j<=S;j++){
			val = b[i] / j;
			list[j].push_back(data(j, val, i, false) );
		}
		for(int j = val-1 ; j >= 0; j--){
			int v = b[i] / (j+1) +1;
			list[v].push_back(data(v, j, i, false) );
		}
	}
    ll ans = 0, mul = 1, wi = 0;
	for(int i=0;i<n;i++){
		mul *= ll(b[i] - a[i]);
		mul %= MM;
	}
	for(int i=2;i<=1000005;i++){
		sort(list[i].begin(), list[i].end());
	}
	for(int i=2;i<=1000005;i++){
		d[i-1] = mul;
		int j;
		for(j = 0; j < list[i].size(); j++){
			int ad = list[i][j].ad;
			if( list[i][j].ch ){ // a
				mul *= div(b[ad] - a[ad]); mul%=MM;

				a[ad] = list[i][j].su;

				mul *= b[ad] - a[ad]; mul%=MM;
			}
			else{ // b
				mul *= div(b[ad] - a[ad]); mul%=MM;

				b[ad] = list[i][j].su;

				mul *= b[ad] - a[ad]; mul%=MM;
			}
		}
		wi = j;
	}
    for (int i = 1000005; i >= 1; i--) {
        for (int j = i + i; j <= 1000005; j+=i) {
            d[i] = (d[i] - d[j] + MM) % MM;
        }
    }
    for (int i = 1; i <= 1000005; i++) {
        ans += (ll) i * d[i];
        ans = ans % MM;
    }
    printf("%lld\n", ans);
    return 0;
}
/*
7
2 222222
20 222220
22 222202
200 222200
202 222022
220 222020
222 222002
*/

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1508 ms 141880 KB Output is correct
2 Correct 1532 ms 141880 KB Output is correct
3 Correct 1504 ms 141880 KB Output is correct
4 Correct 2220 ms 204448 KB Output is correct
5 Correct 2192 ms 204448 KB Output is correct
6 Correct 2236 ms 204448 KB Output is correct
7 Correct 2824 ms 204448 KB Output is correct
8 Correct 2828 ms 204448 KB Output is correct
9 Correct 2820 ms 204448 KB Output is correct
10 Correct 2844 ms 204448 KB Output is correct
11 Memory limit exceeded 492 ms 262144 KB Memory limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

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