AOJ 1325 : Ginkgo Numbers

問題リンク : Ginkgo Numbers | Aizu Online Judge

問題概要 :
Ginkgo Number が与えられる
問題文中で定義されている素数の条件を満たすかどうか判定せよ

解法 :
一番下に書いてあるヒント的なものの2つめを使った
If · = , then (m2 + n2)(x2 + y2) = p2 + q2.

入力でp,qが与えられたとする
(m2 + n2) = a
(x2 + y2) = b
とすると
1 <= a <= sqrt(p2+q2) かつ (p2+q2) は a で割り切られる
上の条件を満たすaを全て試す
aが決まるとbも(p2+q2)/aで求まる

a,bが決まったのでここからm,n,x,yを求める
(m2+n2) = a なのだから、雑に見積もっても

• sqrt(a) <= m <= sqrt(a) である

この範囲をループで全て試す
mが決まるとnも sqrt( a - m2 ) から求まる
a-m2が何かの二乗になっていない場合は求めたいnは存在しないので continue

同様にして、xの範囲もループで決めてyを求める
こうしてm,n,x,yが求まるので、それらが基本となる８つの Ginkgo Numbers でないか確かめ、そうでないなら８つ以外の divisor が存在するので 'C' を出力する

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

bool isEightDivisors(int p,int q,int m,int n){
  if( p ==  1 && q ==  0 ) return true;
  if( p ==  0 && q ==  1 ) return true;
  if( p == -1 && q ==  0 ) return true;
  if( p ==  0 && q == -1 ) return true;
  if( p ==  m && q ==  n ) return true;
  if( p == -n && q ==  m ) return true;
  if( p == -m && q == -n ) return true;
  if( p ==  n && q == -m ) return true;
  return false;
}

#define EPS (1e-8)

bool isSqrt(ll x){
  ll tmp = sqrt(x) + EPS;
  return tmp * tmp == x;
}

bool isPrime(int p,int q){
  int p2 = p * p, q2 = q * q;
  for(int a=1;a*a<=p2+q2;a++) {
    if( ( p2 + q2 ) % a ) continue;
    int b = ( p2 + q2 ) / a;

    int base_a = sqrt(a);
    int base_b = sqrt(b);

    for(int m=-base_a;m<=base_a;m++) {
      if( base_a * base_a > a ) continue;
      int n2 = a - m * m;

      if( !isSqrt(n2) ) continue;

      int n = sqrt(n2);

      if( ( m*m + n*n ) == 0 ) continue;

      if( !( ( m*p + n*q ) % ( m*m+n*n ) == 0 &&
             ( m*q - n*p ) % ( m*m+n*n ) == 0 ) ) continue;

      for(int x=-base_b;x<=base_b;x++){
        if( base_b * base_b > b ) continue;
        int y2 = b - x * x;
        if( !isSqrt(y2) ) continue;
        int y = sqrt(y2);
        
        if( !isEightDivisors(m,n,p,q) && !isEightDivisors(n,m,p,q) ) {
          return false;
        }

        if( !isEightDivisors(x,y,p,q) && !isEightDivisors(y,x,p,q) ) {
          return false;
        }
        
      }
    }
  }
  return true;
}

int main(){
  int T;
  cin >> T;
  rep(_,T){
    int n,m;
    cin >> n >> m;
    puts(isPrime(n,m)?"P":"C");
  }
  return 0;
}