oj.uz

Submission #9790

# Submission time Handle Problem Language Result Execution time Memory
9790 2014-09-28T08:57:39 Z lemonsqueeze Xtreme gcd sum (kriii2_X) C++
0 / 4
 176 ms 64660 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 = 1200;

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

# Verdict Execution time Memory Grader output
1 Correct 148 ms 63868 KB Output is correct
2 Correct 168 ms 63868 KB Output is correct
3 Correct 148 ms 63868 KB Output is correct
4 Correct 140 ms 64000 KB Output is correct
5 Correct 144 ms 64000 KB Output is correct
6 Correct 144 ms 64000 KB Output is correct
7 Correct 148 ms 64000 KB Output is correct
8 Correct 152 ms 64000 KB Output is correct
9 Correct 156 ms 64000 KB Output is correct
10 Correct 160 ms 64000 KB Output is correct
11 Correct 156 ms 64660 KB Output is correct
12 Correct 160 ms 64660 KB Output is correct
13 Correct 164 ms 64660 KB Output is correct
14 Correct 156 ms 64660 KB Output is correct
15 Correct 176 ms 64660 KB Output is correct
16 Incorrect 164 ms 64396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -