oj.uz

Submission #9716

# Submission time Handle Problem Language Result Execution time Memory
9716 2014-09-28T08:20:22 Z lemonsqueeze Xtreme gcd sum (kriii2_X) C++
0 / 4
 144 ms 18532 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 = 1500;

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{
		return wi < l.wi;
	}
};

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 >= 1; 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 *= (b[i] - a[i]);
	for(int i=2;i<=1000000;i++){
		d[i-1] = mul;
		int j;
		for(j = wi; j < list.size() && list[wi].wi == 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 = 1000000; i >= 1; i--) {
        for (int j = i + i; j <= 1000000; j+=i) {
            d[i] = (d[i] - d[j] + MM) % MM;
        }
    }
    for (int i = 1; i <= 1000000; i++) {
        ans += (ll) i * d[i];
        ans = ans % MM;
    }
    printf("%lld\n", ans);
    return 0;
}

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 17124 KB Output is correct
2 Correct 132 ms 17124 KB Output is correct
3 Correct 132 ms 17124 KB Output is correct
4 Correct 136 ms 17380 KB Output is correct
5 Correct 136 ms 17380 KB Output is correct
6 Correct 132 ms 17380 KB Output is correct
7 Correct 136 ms 17380 KB Output is correct
8 Correct 132 ms 17380 KB Output is correct
9 Correct 136 ms 17380 KB Output is correct
10 Correct 140 ms 17380 KB Output is correct
11 Incorrect 144 ms 18532 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

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