Submission #9766

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9766	2014-09-28T08:50:49 Z	lemonsqueeze	Xtreme gcd sum (kriii2_X)	C++	0 / 4	152 ms	18532 KB

X

#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{
		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 >= 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 *= 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	136 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	140 ms	17380 KB	Output is correct
6	Correct	140 ms	17380 KB	Output is correct
7	Correct	144 ms	17380 KB	Output is correct
8	Correct	144 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	Incorrect	152 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	-