猫でもわかるWeb開発・プログラミング

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

トップ > AOJ 1325: Ginkgo Numbers

AOJ 1325: Ginkgo Numbers

はじめに

問題文概訳

  • 適宜説明を付け加えなが訳していく

銀杏数という数字と、その銀杏数の掛け算を定義する。

まずは銀杏数の定義からである。 銀杏数は2つの整数のペアである。 例えば<1, 1>, <-2, 1>, <-3, -1> のようなものが銀杏数である。

銀杏数の掛け算は以下のように定義される

<m, n>・<x. y> = <mx - ny, my + nx>

例えば、<1, 1>・<-2, 1> = <-3, -1> となる。

この定義によると、銀杏数<m, n>に対して、 <1, 0>, <0, 1>, <-1, 0>, <0,-1>, <m, n>, <-n,m>, <-m,-n>, <n,-m> は <m, n> を割り切ることができる。 ここで m2 + n2 > 1 ならば、これら（8つの）の銀杏数はすべて異なる銀杏数になる。

（訳注：m2 + n2 \leq 1 となる例として、m = 1, n = 0 などが考えられるが、この場合は、<m, n> が <1, 0> になってしまったり、<m, n> = <m, -n> になってしまったりして、8個の中で同値なものが出てきてしまう。）

つまり、m2 + n2 > 1 ならば、ある銀杏数<m, n>は、少なくとも8つの銀杏数で割り切れることになる。

これに基づき、銀杏数が「素（そ）である」ことの定義をする。 銀杏数<m, n>がm2 + n2 > 1 を満たし、かつちょうど8つの法を持つとき、 銀杏数 <m, n> は素であるという。

あなたの仕事は、与えられた銀杏数が素かどうかを確かめることである。

銀杏数が素になるかどうかについては、以下の事実が重要になってくる。

  • m2 + n2 > 0 のとき、<p, q>が<m, n>で割り切れること と、 m^2 + n^2 が mp + nq と mq - np の約数であること は同値である。
  • <m, n>・<x, y> = <p, q> なら、(m2 + n2)(x2 + y2) = p2 + q2 である。

（入出力例略）n \leq 20000 とする。

解法

このような数学的な問題を見ると「うっ…」となるかもしれないので、しっかりと情報を整理する。

銀杏数の積の定義から得られる情報

まずはじめに、銀杏数の積が定義されているが、銀杏数の積の計算方法は実装する必要がない。 しかし、必要ない情報かといったらそうでもない。この定義については、<0, 0> は掛け算における0と同じで、どんな銀杏数でも <0, 0> をかけたら答えが <0, 0> になるということはここから把握する必要がある。

「素」という概念についてイメージする

これは要するに、「素数を求めよ」という問題である。自然数に対して素数とは、「1と自分自身でのみ割り切れる数」のことを意味する。銀杏数<m, n>に対してそれが素であるとは、「<1, 0>, <0, 1>, <-1, 0>, <0,-1>, <m, n>, <-n,m>, <-m,-n>, <n,-m> でのみ割り切れる」ということが条件である。

最後に現れた2つの事実に関して理解する

では最後に出てきた、「重要な2つの事実」の意味することとはなんだろうか。

  • m2 + n2 > 0 のとき、<p, q>が<m, n>で割り切れること と、 m^2 + n^2 が mp + nq と mq - np の約数であること は同値である。

「素」のイメージをしてもらったらわかると思うが、「素」かどうか求めるためには、銀杏数の割り算をして割り切れるかということを確認する必要がある。その割り算の部分で、この条件を使う。

  • <m, n>・<x, y> = <p, q> なら、(m2 + n2)(x2 + y2) = p2 + q2 である。

まず、普通に自然数から素数を求めることを考えてみよう。nが素数かどうか求めるためには、1からnの数で割ってみたらよいのである。一方で、銀杏数に置き換えてみると、一体どの範囲の銀杏数で割ったらそれが素と確信できるかどうか掴みづらい。そこでこの2番目の条件が使える。

銀杏数 <p, q> が素かどうか求めようと思う。<x, y> != <0, 0> とすると、上の式において、x2 + y2 \geq 1 であるので、m2 + n2 \leq p2 + q2 である。for文でmとnを決めて、それで <p, q> が割れるかどうか試していくことを考えると、少なくとも m2 \leq < p2 + q2 であるし、mを決めたら、nに関しては、m2 + n2 \leq p2 + q2 であるので、この範囲を調べればよいということがこの式からわかる。

ソースコード

要するに先ほどの範囲の中で割ってみて、<1, 0>, <0, 1>, <-1, 0>, <0,-1>, <m, n>, <-n,m>, <-m,-n>, <n,-m> 以外で割り切れたら素ではない。そうでなかったら素である、と判定する。実際には、割り切れた銀杏数をカウントして、8個だったら素、そうでなかったら素ではないという判定を行っている。

class Main extends MyUtil{
    public static void main(String[] args) throws Exception{
        int n = readInt();
        for (int i = 0; i < n; i++) {
            // 入力は独自クラスを使っている
            int[] in = readIntMap();
            if(isPrime(in[0], in[1])){
                System.out.println("P");
            }else{
                System.out.println("C");
            }
        }
    }
    
    static boolean isPrime(int p, int q){
        int cnt = 0;
        int max_sq = sq(p) + sq(q);
        // ↓ここの探索範囲については前の章で述べた通り
        // また、for文の開始や終了の条件が複雑になるため、
        // m >= 0, n >= 0 だけでループさせて、ループの中で符号を反転させたものも考えている。
        for(int m = 0; m*m <= max_sq; m++){
            for(int n = 0; m*m + n*n <= max_sq; n++){
                // <0, 0> は覗いて考える。
                if(sq(m) + sq(n) == 0) continue;
                
                if(canDivide(p, q, m, n)){
                    cnt++;
                }
                // m = 0 の場合、↑のと重複して数えることになるので除く
                // 以下同様
                if(m != 0 && canDivide(p, q, -m, n)){
                    cnt++;
                }
                if(n != 0 && canDivide(p, q, m, -n)){
                    cnt++;
                }
                if(m != 0 && n != 0 && canDivide(p, q, -m, -n)){
                    cnt++;
                }
            }
        }
        // 8個だった場合は素である
        if(cnt == 8) return true;
        return false;
    }
    
    /**
    * <p, q> が <m, n> で割れるかどうかを確かめる
    */
    static boolean canDivide(int p, int q, int m, int n){
        // 問題文の条件の1番目を式にしただけ
        return (m*p + n*q) % (sq(m) + sq(n)) == 0 && (m*q - n*p) % (sq(m) + sq(n)) == 0;
    }
    
    /**
    * 2乗のための関数
    */
    public static int sq(int i) {
        return i * i;
    }
}