Beta Round #56-D: Savior - komiyamの日記

keyword

問題概要

長さN(<10^6)の数列an(0

条件: 2頂点の値をa,bとする。このとき、∃c in Z s.t. a,b,cの置換x,y,zが原始ピタゴラス数。

解法

10^7以下のピタゴラス数は全列挙できるかも知れない。原始ピタゴラス数はm,nを互いに素で偶奇の異なる整数とするとm^2-n^2, 2*m*n, m^2+n^2で与えられる。なのでそのうち2つがM以下になるような組は(sqrt(M))^2=Mで列挙できる、かもしれない(m^2-n^2も2*m*nも小さくなったりするのでどこで打ちきってよいかがはっきり分からない)。あとはunion findするだけ。

感想

コンテスト中に考えていたこと。

原始ピタゴラス数って前にSRMで見た記憶が。あの時は偶奇で2部グラフにして最大マッチングだったけど今回は無理か。
グラフが作れたらsource検出っぽいことするのか？いやいや、無向グラフだしUnion Findで事足りる。後はピタゴラス数について調べる。
全列挙がO(M)で大体できるとわかる。Custom Testで試したら際どいけど間に合った。
組み始める。入出力が多いので念のために自作readint関数を使おう。完成後提出したらpretestは通った。
同じ値が複数あったときの処理を忘れてた。付け加えたら処理が微妙に重くなってTLEをくらったので探索空間を狭くして再提出(結局無事に通ってくれた)。

inline int readint(){
    int ret = 0, x;
    bool plus = true;
    while(x=getchar(), !('0'<=x&&x<='9' || x=='-'));
    if(x=='-') plus = false;
    else ret = (x&15);
    while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);
    return plus?ret:-ret;
}

const int MAX = 10000001;
vector<int> as;
int pars[1000008];
bool found[10000008];
vector<int> toIdx[10000008];

int getRoot(int x){ return x==pars[x]?x:(pars[x]=getRoot(pars[x]));}
void merge(int x, int y){ pars[getRoot(x)] = getRoot(y); }

void solve(){
    for(int64 m=2; ;m++){
        for(int64 n=1;n<m;n++)if(__gcd(n,m)==1 && ((m&1)^(n&1))){
            int64 a,b,c;
            a = m*m-n*n;
            b = 2*m*n;
            c = m*m+n*n;
            if(a<=MAX && b<=MAX && found[a] && found[b]){
                for(int i=1; i<toIdx[a].size(); i++){
                    merge(toIdx[a][0], toIdx[a][i]);
                }
                for(int i=1; i<toIdx[b].size(); i++){
                    merge(toIdx[b][0], toIdx[b][i]);
                }
                merge(toIdx[a][0], toIdx[b][0]);
            }
            if(a<=MAX && c<=MAX && found[a] && found[c]){
                for(int i=1; i<toIdx[a].size(); i++){
                    merge(toIdx[a][0], toIdx[a][i]);
                }
                for(int i=1; i<toIdx[c].size(); i++){
                    merge(toIdx[c][0], toIdx[c][i]);
                }
                merge(toIdx[a][0], toIdx[c][0]);
            }
            if(c<=MAX && b<=MAX && found[c] && found[b]){
                for(int i=1; i<toIdx[c].size(); i++){
                    merge(toIdx[c][0], toIdx[c][i]);
                }
                for(int i=1; i<toIdx[b].size(); i++){
                    merge(toIdx[b][0], toIdx[b][i]);
                }
                merge(toIdx[c][0], toIdx[b][0]);
            }
            if(min(a,b) > 20000000) return ;
        }
    }
}

int main(){
    int n = readint();
    for(int i=0; i<n; i++){
        as.push_back(readint());
    }
    for(int i=1; i<=n; i++){
        pars[i] = i;
    }
    for(int i=0; i<n; i++){
        found[as[i]] = true;
        toIdx[as[i]].push_back(i+1);
    }
    solve();
    int ans = 0;
    for(int i=1; i<=n; i++){
        if(getRoot(i) == i) ans++;
    }
    printf("%d\n",ans);
    return 0;
}