oj.uz

Submission #9770

# Submission time Handle Problem Language Result Execution time Memory
9770 2014-09-28T08:52:23 Z lemonsqueeze Xtreme gcd sum (kriii2_X) C++
0 / 4
 148 ms 17764 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;
 
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.push_back(data(j, val, i, true) );
		}
		for(int j = val-1 ; j >= 0; j--){
			list.push_back(data(a[i] / (j+1) +1, j, i, true) );
		}
		for(int j=2;j<=S;j++){
			val = b[i] / j;
			list.push_back(data(j, val, i, false) );
		}
		for(int j = val-1 ; j >= 0; j--){
			list.push_back(data(b[i] / (j+1) +1, j, i, false) );
		}
	}
	sort(list.begin(), list.end());
    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++){
		d[i-1] = mul;
		int j;
		for(j = wi; j < list.size() && i == list[j].wi; j++){
			int ad = list[j].ad;
			if( list[j].ch ){ // a
				mul *= div(b[ad] - a[ad]); mul%=MM;

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

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

				b[ad] = list[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 136 ms 17124 KB Output is correct
2 Correct 140 ms 17124 KB Output is correct
3 Correct 132 ms 17124 KB Output is correct
4 Correct 136 ms 17124 KB Output is correct
5 Correct 140 ms 17124 KB Output is correct
6 Correct 144 ms 17124 KB Output is correct
7 Correct 140 ms 17380 KB Output is correct
8 Correct 136 ms 17380 KB Output is correct
9 Correct 136 ms 17380 KB Output is correct
10 Correct 136 ms 17380 KB Output is correct
11 Correct 144 ms 17764 KB Output is correct
12 Correct 144 ms 17764 KB Output is correct
13 Correct 144 ms 17764 KB Output is correct
14 Correct 148 ms 17764 KB Output is correct
15 Correct 148 ms 17764 KB Output is correct
16 Incorrect 144 ms 17764 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 -