これはなにか

paizaの10万登録ありがとうスペシャルWキャンペーンというのがありました。
総括するのが流行っているみたいなので、俺も俺も。
ちなみに、おじさんはC言語のみです。

アルゴリズム

• デカイ配列を用意しておく
• 読み込んだs_i*s_jにマークを付ける
• p_iから数えて、マークまで進んだ数を出力

コード

書き散らかして、どれを提出したのかわからなくなったので（ぉ
多分これだと思うやつ。

i,j,S[1<<20],F[4096];
main(X)
{
    for(;~scanf("%d",F+i++);)
        for(j=*S=*F+2;j<i;S[X<S-F?X:0]=1)
            X=F[i-1]*F[j++];

    for(i=1;++i-*S;printf("%d\n",j-X))
        for(X=j=F[i];!S[j];++j);
}

fuyutsubakiさんのと基本同じですな。

解説という名の蛇足

• 配列FにM, N, p_m, s_nを読み込む。
• M = F[0], N = F[1], p_m = F[2 ..F[0]+2], s_n = F[F[0]+2 .. F[1]+2]に入っていることになります。 (*SにF[0]+2 == s_0の添字を入れてます)
• 読み込んでいる最中に、X = s_i * s_jを計算して、デカイ配列Sに入るようならS[X]を1にします。 (入るかどうかチェックするのに、デカイ配列SのサイズをS-Fで計算していますが、逆(F-S)じゃないかと思われますが、手元のgccがそーいうコードを落とすのだから、しょうがない。)
• p_mに対して、デカイ配列S[p_m]から0以外が出るまでの数を数えて出力します。

自己批判

• 最初、コードサイズのことを、「実行ファイルのバイト数」だと思いこんで、printfをputcharに書き換えたりして、考えすぎた。
• 1000000にこだわりすぎた。
• qsort関数で副作用をうまく利用してやろうと考えて、考えすぎた。
• 配列をcharとして扱って、マークまでの数をstrlen関数で求めようなどとして、考えすぎた。
• s_iとs_jが素なら中国の剰余定理が使えるんじゃね？と思って、興味が横道にそれた。
• 基本ゴルファーでないのに、無理しすぎた。

現場からは以上です。