Submission #9796

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9796	2014-09-28T08:58:58 Z	lemonsqueeze	Xtreme gcd sum (kriii2_X)	C++	0 / 4	2844 ms	262144 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 = 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

#	Verdict	Execution time	Memory	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

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