kmjp's blog

競技プログラミング参加記です

Saiko~ No Contesuto #03 : 歯車と箱

歯車ネタyukicoderでも見たな…。
https://www.hackerrank.com/contests/camypapercon03/challenges/gear-and-box

問題

N個(偶数)の歯車がある。
各歯車の歯数はZ[i]である。

2つの未使用の歯車a,bを組み合わせると減速比Z[b]/Z[a]の減速機構が作れる。
また減速機構を2つ合わせると、減速比がその積となる減速機構を作れる。

N個の歯車をすべて使い、単一の減速機構を作る。
その際の減速比の最大値を求め、有理数の形で出力せよ。

回答

Z[i]のうち大きい方半分を小さい方半分で割った答えが解となる。
求めるのは約分した上で10^9+7の剰余を取った値になるので、それぞれ素因数分解して各素因数の乗数を求めて分母分子の差を取ればよい。

int N;
int Z[101010];
int num[101010][2];
ll mo=1000000007;

const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		divp[i]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	cin>>N;
	FOR(i,N) cin>>Z[i];
	sort(Z,Z+N);
	reverse(Z,Z+N);
	
	FOR(i,N) {
		x=Z[i];
		while(x>1) {
			num[divp[x]][(i>=N/2)]++;
			x/=divp[x];
		}
	}
	
	ll v[2]={1,1};
	for(i=2;i<=101000;i++) {
		FOR(j,abs(num[i][0]-num[i][1])) (v[num[i][0]<num[i][1]]*=i)%=mo;
	}
	_P("%lld %lld\n",v[0],v[1]);
}

まとめ

歯車は出てきたけど、箱とは…?