平方数とは平方根が整数の数のことだ。小さい順で並べていくと、0, 1, 4, 9, 16, 25, 36, … となる。あるいは、素因数分解して、すべての素因数の指数が偶数である場合も平方数になる。たとえば、36 = 22x32、素因数の指数がそれぞれ2であるので、36は平方数といえる。平方根を計算することは結構時間がかかるので、素因数が分かるのであれば、素因数の指数を調べるほうがはるかに高速。
1. 問題
n (0<n<=200000) 個の整数（絶対値は1018よりも小さいが、すべての素因数は30以下。）が与えられた時に、n個の中から任意の2つを選んで、その積が平方数となる（組合せの）数Xを、n個の中から任意の3つを選んで、その積が平方数となる（組合せの）数Yを求め。
2. 実例
例をもって説明する。
たとえば、3つの整数 2, -2, 2 が与えられた時、2×2 = 4 になるので、X = 1。また明らかに Y = 0。
簡単だな、と思うかもしれないが、データの個数が20万、個々のデータの値の大きさを考えると、そう容易く解けないはずだ。しかも、実行時間は3秒に制限されている。
20万個のデータすべてをここに書き出すことは非現実的だが、20万個のデータが何百組も与えられても、3秒以内に計算を終了させ、正解を出すプログラムを作ることが簡単ではない。すべては高速性にかかってくる。
下は多少複雑な例。それでもデータの個数は100でしかない。
100
64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117
649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826
809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 470
45881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889
594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729
15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 17
71561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24
137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881
148035889 594823321
答えは、X=4950 Y=161700。
3. 計算法
まず、1～2500000の間の、素因数が30以下のすべての値に対し、エラトステネスのふるいを応用して、素因数分解をしておく。2500000を超えた入力値に対しては、単純に１つ１つ素因数分解をしておく。
ただ、本問題では素因数の指数の奇偶性が問題になるので、個々の素因数に対応して、以下のビットパターンを採用する。
最下位ビットから bitpat[11] = { マイナス, 2の数＆1, 3の個数＆1, 5の個数＆1, 7の個数＆1, 11の個数＆1, 13の個数＆1, 17の個数＆1, 19の個数＆1, 23の個数＆1, 29の個数＆1 };
「マイナス」はデータが負数を表すビット、
「2の数＆1」は素因数2の指数が奇数なら1、偶数なら0になる。
「3の数＆1」は素因数3の指数が奇数なら1、偶数なら0になる。
などを意味する。
例えば、6のビットパターンは110、-6のビットパターンは111、10のビットパターンは1010、平方数のビットパターンは0。
データの積を取ることは、すなわち、ビットパターンの XOR 計算にほかならない。そのXORの結果がゼロになれば平方数、ゼロ以外であれば非平方数となる。
また、入力データを値がゼロのものとそうでないものに分ける。値がゼロのデータの数がzだとすると、XとYに相当する部分は以下のように算出する。
X = nC2 – n-zC2 = z(2n-1-z)/2
Y = nC3 – n-zC3
あとは、値がゼロ以外のデータについてのみ、XとYの値を算出し、上の値に足し加えておけばOK。
4. 結果
書くのは嫌になるほど、多くのことをトライして、最終的に実行時間を0.480秒に押さえ、現時点でのランク１位にできた。
細かいことは省略するが、ヒントになるものをリストアップしておく。
- 入力の値に対するビットパターンは2047以下。つまり、異なる入力データの数は2048通りしかない。
- XOR計算 a^b = 0 となるa, bは、a = bに限る。a^b^c = 0となるa, b, cは a^b = c に限る。従って、異なる2048個の値から、任意の２つを取り出してXORがゼロになる計算は2048回（O(n)）で済むし、任意の３つを取り出してXORがゼロになる計算は2048×2048回（O(n2)）で済む。
- 入力データを平方数と非平方数に分けた。平方数同士では、XORがゼロになる。平方数と非平方数とのXORはゼロにならない。非平方数と非平方数とのXORがゼロになるのは、その２つの非平方数が等しい場合に限る。
- 入力データの処理にscanf()ではなく、read()関数を使った。getchar()を使ってランク2にできたが、1位になるには、read()を使ってしまった。
- 計算のオーバーフローに気をつけよう。整数同士の積に64ビット整数を使おう。
5. ソースの一部
typedef long long llong;
typedef unsigned short ushot
#define MAX 2500000
ushot bitpat[MAX+5];
ushot pp[10] = { 2,3,5,7,11,13,17,19,23,29 };
/* 1～MAXまでの各整数に対するビットパターン */
void sieve(void)
{
register int i, j;
int k, p;
ushot b;
for (k = 0; k < 10; k++) {
p = pp[k], b = 1 << (k+1);
for (j = p; j <= MAX; j *= p) {
for (i = j; i <= MAX; i += j) {
if (bitpat[i] & b) bitpat[i] &= ~b;
else bitpat[i] |= b;
}
}
}
}
/* MAXを超えた値に対するビットパターン */
ushot factor(llong n)
{
int k, p, m;
ushot ans;
ans = 0;
if (!(n & 1)) {
m = 0;
do n >>= 1, m++;
while (!(n & 1));
if (m & 1) ans |= 2;
}
for (k = 1; n > 1 && k < 10; k++) {
p = pp[k];
if (!(n 0x7fff0dc99530)) {
m = 0;
do { m++; n /= p; }
while (n 0x7fff0dc99530 == 0);
if (m & 1) ans |= 1 << (k+1);
}
}
return ans;
}
XとYを算出する部分（分かりやすくするため、ソースの一部を書き直した。ソースそのものとは異なる）。なお、freq[a]はビットパターンがaである入力データの個数を示す。
X = Y = 0;
for (i = 1; i < 2048; i++) {
if (freq[i]) {
X += ((llong)freq[i]*(freq[i]-1))/2;
for (j = i+1; j < 2048; j++) {
if (freq[j]) {
if ((i^j) > j && freq[i^j]) Y += (llong)freq[i]*freq[j]*freq[i^j];
}
}
}
}
