SRM477 Medium: PythTriplets

keyword

ピタゴラス数　2部グラフ　マッチング　C++

概要

200個以下の正の数字が与えられる(重複あり)。このとき、互いに素で2乗和が平方数になるようなペアがいくつ取り出せるか求める問題。
ペアは必ず偶数と奇数からなる。何故なら偶数と偶数のペアは互いに素でなく、奇数と奇数の2乗和は2で丁度1回割りきれるからである。なので偶数と奇数に分ければよい。
2部グラフの動作確認の意味で解いたけど実行時間は一番遅いので11ms位だった。

inline bool isSq(int x, int y){
    ll xx=x, yy=y, zz=xx*xx+yy*yy;
    return (ll)(sqrt(zz)+0.3)*(ll)(sqrt(zz)+0.3) == zz;
}

inline bool check(int x, int y){
    return isSq(x,y) && (__gcd(x,y)==1);
}

int findMax(vector <string> stick) {
    int i, j;
    int x;
    vector<int> odds, evens;
    string st = "";
    REP(i,SZ(stick))st+=stick[i];
    istringstream is(st);
    while(is>>x){
        if(x%2) odds.PB(x);
        else evens.PB(x);
    }
    int n = SZ(odds), m = SZ(evens);
    vector<vector<int> > bigraph(n);
    REP(i,n)REP(j,m)if(check(odds[i], evens[j])){
        bigraph[i].PB(j);
    }

    return BipartiteMatchingByList(bigraph);
}