Submission #9679

#	Time	Username	Problem	Language	Result	Execution time	Memory
9679		myungwoo	Xtreme gcd sum (kriii2_X)	C++14	0 / 4	0 ms	262144 KiB

X

#include<stdio.h>
#include<memory.h>
#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;
conv sun[21000000];

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[cnt++]=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[cnt++]=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: 0 / 1
• Subtask 2: 0 / 3