1325:Ginkgo Numbers

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

二つの整数(m,n)の組をGinkgo numberと呼ぶ。
· =
をGinkgo numberの掛け算とする。
また、 · = であるとき、はの約数である。さらに、あるGinkgo numberが<1, 0>, <0, 1>, <-1, 0>, <0,-1>, , <-n,m>, <-m,-n>, 以外に約数を持たないとき、は素数である。与えられたGinkgo numberが素数であるかどうか判定せよ。

また、Ginkgo numberについて以下のことが成立する。
m^2+n^2>0のときm^2+n^2がmp+nqとmq-npの約数ならばはの約数
· = ならば (m^2 + n^2)(x^2 + y^2) = p^2 + q^2

与えられたGinkgo numberの約数の個数が8個以下であれば素数である。あるがの約数かどうかは、問題文の下のほうに書いてある条件の1つめを使えば求められる。また、調べる範囲は２つ目の条件によって限定できる。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void){

  int t;
  cin >> t;

  while(t--){
    int p,q;
    cin >> p >> q;
    int tmp=p*p+q*q,cnt=0;

    for(int n=0;n*n<=tmp;n++){
      for(int m=0;m*m<=tmp;m++){
        if(m*m+n*n<1)continue;
        if((m*p+n*q)%(m*m+n*n)==0 && (m*q-n*p)%(m*m+n*n)==0)cnt++;
      }
    }

    if(cnt*2<=8)cout << "P" << endl;
    else cout << "C" << endl;
  }
  return 0;
}