平方数とは平方根が整数の数のことだ。小さい順で並べていくと、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 が与えられた時、2x2 = 4 になるので、X = 1。また明らかに Y = 0。
 簡単だな、と思うかもしれないが、データの個数が20万、個々のデータの値の大きさを考えると、そう容易く解けないはずだ。しかも、実行時間は3秒に制限されている。
 20万個のデータすべてをここに書き出すことは非現実的だが、20万個のデータが何百組も与えられても、3秒以内に計算を終了させ、正解を出すプログラムを作ることが簡単ではない。すべては高速性にかかってくる。

下は多少複雑な例。それでもデータの個数は100でしかない。

答えは、X=4950 Y=161700。

3. 計算法
 まず、1~2500000の間の、素因数が30以下のすべての値に対し、エラトステネスのふるいを応用して、素因数分解をしておく。2500000を超えた入力値に対しては、単純に1つ1つ素因数分解をしておく。
 ただ、本問題では素因数の指数の奇偶性が問題になるので、個々の素因数に対応して、以下のビットパターンを採用する。

 最下位ビットから 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秒に押さえ、現時点でのランク1位にできた。

細かいことは省略するが、ヒントになるものをリストアップしておく。

  1. 入力の値に対するビットパターンは2047以下。つまり、異なる入力データの数は2048通りしかない。
  2. XOR計算 a^b = 0 となるa, bは、a = bに限る。a^b^c = 0となるa, b, cは a^b = c に限る。従って、異なる2048個の値から、任意の2つを取り出してXORがゼロになる計算は2048回(O(n))で済むし、任意の3つを取り出してXORがゼロになる計算は2048x2048回(O(n2))で済む。
  3. 入力データを平方数と非平方数に分けた。平方数同士では、XORがゼロになる。平方数と非平方数とのXORはゼロにならない。非平方数と非平方数とのXORがゼロになるのは、その2つの非平方数が等しい場合に限る。
  4. 入力データの処理にscanf()ではなく、read()関数を使った。getchar()を使ってランク2にできたが、1位になるには、read()を使ってしまった。
  5. 計算のオーバーフローに気をつけよう。整数同士の積に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];
            }
        }
    }
}

Comments are closed.

Post Navigation