SRM 661 div1 easy:MissingLCM - mayoko’s diary

SRM661には不参加です。一応easyは自力で解けましたが結構時間かかってしまいました。medはこれから解きます。

問題

解法

C++で500ms近くかかっています。想定解とは違うかも。

サンプルにヒントがあるように2*Nという数はキーとなる数字です(答えではないですが)。

なぜならば,

N+1, N+2, ..., 2*N

の中に必ず1, 2, 3, ..., Nに対応する倍数があるからです(例えば2の倍数はN+1かN+2の中に必ずあります。また,5の倍数はN+1, N+2, N+3, N+4,N+5の中に必ずあります。一般にkに対してN+1, N+2, ..., N+kの中に必ずkの倍数があります)。

よって,N+1から2*Nの最小公倍数は,1からNの最小公倍数以上になっていることがわかります。

問題文に「問題の条件を満たすようなMは必ず存在する」と書いてあることから,Mは絶対に2*N以下でなければなりません。

この考察により,Mはたかだか2*Nであることがわかりました。Nは10^6とそこそこ小さいので,全探索することを考えます。

N+1〜Mの最小公倍数が1〜Nの最小公倍数になるためには,各素因数p1, ..., pmについて,p1の指数部,p2の指数部,..., pmの指数部がすべて1〜Nの最小公倍数とN+1〜2*Nの最小公倍数とで同じになっていることが必要十分条件です。

よって,これをそこそこ高速で調べられれば良いです。
最初に

for (int i = 2; i < 2*MAXN; i++) {
    if (prime[i] == 0) {
        for (int j = 2; j * i < 2*MAXN; j++) {
            prime[i*j] = i;
        }
    }
}

と初期化をしておけば,prime[a]にはaが素数の場合には0が入って合成数の場合にはaを割り切る最大の素数が入るので素因数分解はたかだかO(log N)で実行でき,これでaの各素因数の指数を求めることが出来ます。

const int MAXN = 1000100;
int should[2*MAXN];
int prime[2*MAXN];

class MissingLCM {
public:
    int getMin(int N) {
        for (int i = 2; i < 2*MAXN; i++) {
            if (prime[i] == 0) {
                for (int j = 2; j * i < 2*MAXN; j++) {
                    prime[i*j] = i;
                }
            }
        }
        for (int i = 2; i <= N; i++) {
            map<int, int> divs;
            int tmp = i;
            while (prime[tmp]) {
                divs[prime[tmp]]++;
                tmp /= prime[tmp];
            }
            divs[tmp]++;
            for (auto el : divs) {
                should[el.first] = max(should[el.first], el.second);
            }
        }
        int cnt = 0;
        for (int i = 0; i < MAXN; i++) if (should[i]) cnt++;
        for (int M = N+1; ; M++) {
            map<int, int> divs;
            int tmp = M;
            while (prime[tmp]) {
                divs[prime[tmp]]++;
                tmp /= prime[tmp];
            }
            divs[tmp]++;
            for (auto el : divs) {
                if (should[el.first] > 0 && should[el.first] <= el.second) {
                    cnt--;
                    should[el.first] = 0;
                }
            }
            if (cnt == 0) return M;
        }
    }
};