Pの競プロ記

競技プログラミングに関することを書きます。

AOJ 1325 Ginkgo Numbers

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1325


解法


この問題ではガウス整数を扱っていることが分かります。
http://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E6%95%B4%E6%95%B0#.E3.82.AC.E3.82.A6.E3.82.B9.E7.B4.A0.E6.95.B0

解法としては、ガウス素数かどうか判定させるか、与えられた式を変形して値を代入する2パターンあります。


ソースコード


ガウス素数判定による解法

#include <iostream>
#include <cstring>

using namespace std;

bool isPrime[20000 + 1];

bool isGaussianPrime(int a, int b) {
  if(a < 0) a = -a;
  if(b < 0) b = -b;
  if(a == 0) return b % 4 == 3 && isPrime[b];
  if(b == 0) return a % 4 == 3 && isPrime[a];
  return isPrime[a * a + b * b];
}

int main() {
  memset(isPrime, true, sizeof(isPrime));
  isPrime[0] = isPrime[1] = false;
  for(int i = 2; i * i < 20000 + 1; i++) {
    if(!isPrime[i]) continue;
    for(int j = i * i; j < 20000 + 1; j += i) {
      isPrime[j] = false;
    }
  }

  int T;
  cin >> T;
  while(T--) {
    int m, n;
    cin >> m >> n;
    cout << (isGaussianPrime(m, n) ? "P" : "C") << endl;
  }
  return 0;
}

・式変形して値を代入していく解法

#include <iostream>

using namespace std;

int main() {
  int T;
  int m, n;
  cin >> T;
  while(T--) {
    cin >> m >> n;
    int count = 0;
    for(int i = -150; i <= 150; i++) {
      for(int j = -150; j <= 150; j++) {
        if(i * i + j * j == 0) continue;
        if((i * m + j * n) % (i * i + j * j)) continue;
        if((i * n - j * m) % (i * i + j * j)) continue;
        count++;
      }
    }
    cout << (count == 8 ? "P" : "C") << endl;
  }
  return 0;
}