kmjp's blog

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

Lyft Level 5 Challenge 2018 - Elimination Round : D. Divisors

これはなんとか解けて良かったね。
http://codeforces.com/contest/1033/problem/D

問題

N個の整数A[i]が与えられる。
各整数は合成数であり、約数が3~5個であることがわかっている。

Aのすべての積における、約数はいくつか。

解法

Aの積を素因数分解できれば、約数の数は容易に求められる。
A[i]の約数が3個・5個になるのは、A[i]が素数の平方数か4乗数になる場合である。
A[i]の約数が4個になるケースが問題で、素数の立方数になる場合と、2つの素数の積となる場合がある。

最後のケースは置いておいて、素数の平方数~4乗数になるケースを先に片づけよう。
先に1~10^6の3乗・4乗の値を列挙しておけば、立方数・4乗数になるケースは容易に判定できる。
4乗数になるケースを除いておけば、A[i]が平方数になるのはA[i]が素数の2乗のときだけなので、これは単純に平方根が整数になるか判定すればよい。

Aのうち、2つの素数の積となるものがいくつか残った場合を考える。
Aの上限が大きいので、愚直に素因数分解するのは間に合わない。
この場合、2つの素数の積A[i]に対し、A[j]を総当たりでGCD(A[i],A[j])を求めてみよう。
GCD(A[i],A[j])が2以上A[i]未満なら、それはA[i]の素因数の一つとなるので素因数分解が成功する。

問題はそのようなA[j]が無い場合だが、この場合このA[i]の2つの素因数を素因数とする別のA[j]が存在しないことになるので、具体的な素因数の値はわからなくても、Aの積におけるそれらの素因数の次数はそれぞれ1であることが確定する。

これで各素因数の次数がわかるので、あとは約数の数を求めるだけ。

ll issq(ll V) {
	ll a=sqrt(V);
	for(ll b=a-2;b<=a+2;b++) if(b*b==V) return b;
	return 0;
}

unordered_map<ll,int> S[5];
map<ll,int> M,M2;
int N;
ll A[501];
ll mo=998244353;
int F[501];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=2;;i++) {
		ll a=i;
		double b=i;
		a*=i;
		a*=i;
		b*=i;
		b*=i;
		if(b>3e18) break;
		S[3][a]=i;
		a*=i;
		b*=i;
		if(b<3e18) S[4][a]=i;
	}
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		if(S[4].count(A[i])) M[S[4][A[i]]]+=4;
		else if(S[3].count(A[i])) M[S[3][A[i]]]+=3;
		else if(issq(A[i])) M[issq(A[i])]+=2;
		else {
			F[i]=1;
		}
	}
	
	
	FOR(i,N) {
		FOR(j,N) if(F[i]) {
			ll g=__gcd(A[i],A[j]);
			if(1<g && g<A[i]) {
				F[i]=0;
				M[g]++;
				M[A[i]/g]++;
			}
		}
		if(F[i]) M2[A[i]]++;
	}
	
	ll ret=1;
	FORR(m,M) ret=ret*(m.second+1)%mo;
	FORR(m,M2) ret=ret*(m.second+1)*(m.second+1)%mo;
	cout<<ret<<endl;
	
}

まとめ

こういう問題良く思いつくね。