TopCoder SRM 668 Div2 Hard AnArray

今回Div2は割と簡単目。
http://community.topcoder.com/stat?c=problem_statement&pm=13994

問題

N要素の整数列A[i]と正整数Kが与えられる。
0≦p＜q＜r＜NかつA[p]*A[q]*A[r]が0となるような(p,q,r)の対の数を求めよ。

解法

qを大きい順に、(p,q)を総当たりしていく。
A[p]*A[q]が決まると、条件を満たすA[r]はs = K/GCD(K,A[p]*A[q])の倍数であることがわかる。
A[r]のうち、sの倍数であるものの個数をnum[s]とすると、A[p]*A[q]に対しrの候補はnum[s]個となる。

各qを処理し終わったら、以後はそのqは以降のqの処理をする際のA[r]の候補となる。
よってA[q]の約数tそれぞれに対しnum[t]をインクリメントしていけば良い。

int num[1010100];
class AnArray {
	public:
	int N;
	vector<ll> enumdiv(ll n) {
		vector<ll> S;
		for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
		sort(S.begin(),S.end());
		return S;
	}
	
	int solveProblem(vector <int> A, int K) {
		N=A.size();
		int i,x,y;
		ZERO(num);
		FORR(r,A) r=__gcd(r,K);
		
		ll ret=0;
		for(y=N-1;y>=0;y--) {
			FOR(x,y) {
				int a=(int)__gcd(1LL*A[x]*A[y],(ll)K);
				ret += num[K/a];
			}
			
			auto v=enumdiv(A[y]);
			FORR(r,v) num[r]++;
		}
		return (int)ret;
		
	}
}

まとめ

えらいシンプルな問題名だな。