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]が素数の平方数か４乗数になる場合である。
A[i]の約数が4個になるケースが問題で、素数の立方数になる場合と、２つの素数の積となる場合がある。

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

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

問題はそのようなA[j]が無い場合だが、この場合このA[i]の２つの素因数を素因数とする別の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;
	
}

まとめ

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