답안 #9668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
9668	2014-09-28T08:00:07 Z	myungwoo	Xtreme gcd sum (kriii2_X)	C++14	1 / 4	664 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 {
	int ix, val, pv; // convert row, column, value, previous index
}im;

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

void make(int ix){
	int 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("%d%d", &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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	17008 KB	Output is correct
2	Correct	0 ms	17008 KB	Output is correct
3	Correct	0 ms	17008 KB	Output is correct
4	Correct	0 ms	17008 KB	Output is correct
5	Correct	4 ms	17008 KB	Output is correct
6	Correct	0 ms	17008 KB	Output is correct
7	Correct	0 ms	17008 KB	Output is correct
8	Correct	0 ms	17008 KB	Output is correct
9	Correct	0 ms	17008 KB	Output is correct
10	Correct	0 ms	17008 KB	Output is correct
11	Correct	48 ms	17588 KB	Output is correct
12	Correct	52 ms	17588 KB	Output is correct
13	Correct	48 ms	17588 KB	Output is correct
14	Correct	48 ms	17588 KB	Output is correct
15	Correct	48 ms	17588 KB	Output is correct
16	Correct	8 ms	17200 KB	Output is correct
17	Correct	36 ms	17392 KB	Output is correct
18	Correct	40 ms	17588 KB	Output is correct
19	Correct	16 ms	17392 KB	Output is correct
20	Correct	28 ms	17392 KB	Output is correct
21	Correct	44 ms	17588 KB	Output is correct
22	Correct	44 ms	17588 KB	Output is correct
23	Correct	48 ms	17588 KB	Output is correct
24	Correct	48 ms	17588 KB	Output is correct
25	Correct	48 ms	17588 KB	Output is correct

Subtask #2

0.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	17200 KB	Output is correct
2	Correct	4 ms	17200 KB	Output is correct
3	Correct	4 ms	17200 KB	Output is correct
4	Correct	0 ms	17200 KB	Output is correct
5	Correct	0 ms	17200 KB	Output is correct
6	Correct	4 ms	17200 KB	Output is correct
7	Correct	0 ms	17200 KB	Output is correct
8	Correct	0 ms	17200 KB	Output is correct
9	Correct	4 ms	17200 KB	Output is correct
10	Correct	0 ms	17200 KB	Output is correct
11	Correct	656 ms	53876 KB	Output is correct
12	Correct	652 ms	53876 KB	Output is correct
13	Correct	652 ms	53876 KB	Output is correct
14	Correct	664 ms	53876 KB	Output is correct
15	Correct	664 ms	53876 KB	Output is correct
16	Correct	60 ms	19316 KB	Output is correct
17	Correct	88 ms	21620 KB	Output is correct
18	Memory limit exceeded	216 ms	262144 KB	Memory limit exceeded
19	Halted	0 ms	0 KB	-