Submission #9709

#	Time	Username	Problem	Language	Result	Execution time	Memory
9709		myungwoo	Xtreme gcd sum (kriii2_X)	C++14	4 / 4	2396 ms	177000 KiB

X

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

typedef long long lld;

int n, se[11111][2], gap[11111];
int phi[1000002], top[1000002], inv[1000002], cnt, mx, gop=1, zcn, dap;
int ix[MX], pv[MX];

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

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

int main(){
	int i, j, p, q;
	scanf("%d", &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=1; i<=mx; i++)inv[i]=pow(i,mod-2);
	for(i=mx; i>=1; i--){
		for(j=top[i]; j>=0; j=pv[j]){
			p=ix[j], q=se[p][1]/i-se[p][0]/i;
			if(gap[p]==0)zcn--;
			else gop=((lld)gop*inv[gap[p]])%mod;
			gap[p]=q;
			if(q==0)zcn++;
			else gop=((lld)gop*q)%mod;
		}
		if(zcn==0){
			dap+=(lld)gop*phi[i]%mod;
			if(dap>=mod)dap-=mod;
		}
	}
	printf("%d", dap);
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3