Submission #9657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9657	2014-09-28T07:53:11 Z	myungwoo	Xtreme gcd sum (kriii2_X)	C++14	1 / 4	764 ms	262144 KB

X

#include<stdio.h>
#include<memory.h>
#include<vector>
#define min2(a,b) ((a)>(b)?(b):(a))
#define mod 1000000007
using namespace std;

typedef long long lld;

struct conv {
	lld ix, val, pv; // convert row, column, value, previous index
}im;

lld phi[1000002], top[1000002], cnt, n, se[11111][2], gap[11111], mx, gop=1, zcn, dap;
vector<conv> sun;

void make(lld ix){
	lld i, j, a;
	for(i=1; i*i<=se[ix][1]; i++){
		im.ix=ix, a=i, im.val=se[ix][1]/i-se[ix][0]/i, im.pv=top[a];
		top[a]=cnt++, sun.push_back(im);
	}
	j=se[ix][0]/i, i=se[ix][1]/i;
	for(; i>=1;){ // 몫 = 3
		if(j==0){
			a=se[ix][1]/i;
			im.ix=ix, im.val=se[ix][1]/a-se[ix][0]/a, im.pv=top[a];
			i--;
		}
		else{
			a=min2(se[ix][0]/j, se[ix][1]/i);
			im.ix=ix, im.val=se[ix][1]/a-se[ix][0]/a, im.pv=top[a];
			if(se[ix][0]/j == se[ix][1]/i)i--, j--;
			else if(se[ix][0]/j > se[ix][1]/i)i--;
			else j--;
		}
		top[a]=cnt++, sun.push_back(im);
	}
}

lld pow(lld a, lld b){
    lld v = a, ret = 1;
    for (;b;b>>=1,v=v*v%mod) if(b&1) ret=ret*v%mod;
    return ret;
}

int main(){
	lld i, j, p, q;
	scanf("%lld", &n), zcn=n;
	memset(top, -1, sizeof(top));
	for(i=0; i<n; i++){
		scanf("%lld%lld", &se[i][0], &se[i][1]), se[i][0]--;
		make(i);
		if(se[i][1]>mx)mx=se[i][1];
	}
	phi[1]=1;
	for(i=2; i<=mx; i++){
		if(phi[i]==0){
			phi[i]=i-1;
			if(i>1000)continue;
			for(j=i*i; j<=mx; j+=i)phi[j]=i;
		}
		else{
			p=phi[i];
			if(i%(p*p)==0)phi[i]=p*phi[i/p];
			else phi[i]=(p-1)*phi[i/p];
		}
	}
	for(i=mx; i>=1; i--){
		for(j=top[i]; j>=0; j=sun[j].pv){
			p=sun[j].ix, q=sun[j].val;
			if(gap[p]==0)zcn--;
			else gop=(gop*pow(gap[p],mod-2))%mod;
			gap[p]=q;
			if(q==0)zcn++;
			else gop=(gop*q)%mod;
		}
		if(zcn==0){
			dap+=gop*phi[i]%mod;
			if(dap>=mod)dap-=mod;
		}
	}
	printf("%lld", dap);
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	17096 KB	Output is correct
2	Correct	0 ms	17096 KB	Output is correct
3	Correct	4 ms	17096 KB	Output is correct
4	Correct	0 ms	17096 KB	Output is correct
5	Correct	0 ms	17096 KB	Output is correct
6	Correct	0 ms	17096 KB	Output is correct
7	Correct	0 ms	17096 KB	Output is correct
8	Correct	0 ms	17096 KB	Output is correct
9	Correct	0 ms	17096 KB	Output is correct
10	Correct	4 ms	17096 KB	Output is correct
11	Correct	52 ms	18252 KB	Output is correct
12	Correct	52 ms	18252 KB	Output is correct
13	Correct	48 ms	18252 KB	Output is correct
14	Correct	48 ms	18252 KB	Output is correct
15	Correct	48 ms	18252 KB	Output is correct
16	Correct	4 ms	17480 KB	Output is correct
17	Correct	36 ms	17676 KB	Output is correct
18	Correct	48 ms	18252 KB	Output is correct
19	Correct	16 ms	17676 KB	Output is correct
20	Correct	24 ms	17676 KB	Output is correct
21	Correct	44 ms	18252 KB	Output is correct
22	Correct	56 ms	18252 KB	Output is correct
23	Correct	48 ms	18252 KB	Output is correct
24	Correct	52 ms	18252 KB	Output is correct
25	Correct	52 ms	18252 KB	Output is correct

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	17480 KB	Output is correct
2	Correct	0 ms	17480 KB	Output is correct
3	Correct	0 ms	17480 KB	Output is correct
4	Correct	0 ms	17480 KB	Output is correct
5	Correct	4 ms	17480 KB	Output is correct
6	Correct	0 ms	17480 KB	Output is correct
7	Correct	0 ms	17480 KB	Output is correct
8	Correct	4 ms	17480 KB	Output is correct
9	Correct	4 ms	17480 KB	Output is correct
10	Correct	0 ms	17480 KB	Output is correct
11	Correct	756 ms	90828 KB	Output is correct
12	Correct	748 ms	90828 KB	Output is correct
13	Correct	760 ms	90828 KB	Output is correct
14	Correct	756 ms	90828 KB	Output is correct
15	Correct	764 ms	90828 KB	Output is correct
16	Correct	72 ms	21708 KB	Output is correct
17	Correct	92 ms	26316 KB	Output is correct
18	Memory limit exceeded	264 ms	262144 KB	Memory limit exceeded
19	Halted	0 ms	0 KB	-