SRM661 Div1 Easy MissingLCM

2015/06/24 (Wed) SRM 数学

問題

問題文

$ \newcommand{\lcm}[1]{\operatorname{lcm} #1} $ 自然数 $N$ が与えられる. $N$ より大きい $M$ であって, $\lcm(1,2, \cdots ,M) = \lcm(N+1,N+2, \cdots ,M)$ となる最小のものを求めなさい.

方針

整数 $A, B$ を素因数分解して $ A = 2^{a_0} 3^{a_1} 5^{a_2} \cdots $, $ B = 2^{b_0} 3^{b_1} 5^{b_2} \cdots $ のように表すと, $ \lcm(N,M) = 2^{\max( a_0, b_0)} 3^{\max( a_1, b_1)} 5^{\max( a_2, b_2)} \cdots $ となる.これを見ると,各素因数の指数が,$N+1$ から $M$ までで $1$ から $M$ までの指数に届かないといけないのがわかる. でも,$M$ の素因数分解に現れる素数の最大値は小さくしたほうが良い. そのとき考えないといけないのは $N$ 以下の素数のべき乗の倍数であって,それが $N$ 以下の素数の倍数が $1$ から $M$ までに含まれているはず. それを含めた上でさらに上の条件を満たし,そして最小化するには,$2$ 倍したものを使えばいい.

説明もコードもとてもわかりにくい…

実装

vector<int> EratosthenesSieve(int n){
    vector<int> ps(n+1);
    loop(i,2,n+1) ps[i] = i;
    for (int i = 2; i*i <= n; ++i)
        if (ps[i])
            for (int j = i*i; j <= n; j+=i)
                ps[j] = 0;
    ps.erase(remove(all(ps),0), ps.end());
    return ps;
}

class MissingLCM {
public:
    ll llpow(ll x, ll y){
        if(y==0) return 1;
        ll t = llpow(x,y/2);
        if(y&1) return t*t*x; else return t*t;
    }
    int getMin(int N_) {
        ll N = N_;
        vector<int> ps = EratosthenesSieve(N+10);
        ll res = N+1;
        for(auto & p : ps){
            if(p > N) continue;
            int e = 0;
            while(llpow(p,e) <= N) e++;
            res = max(res,2*llpow(p,e-1));
        }
        return res;
    }
};