ABC280 D - Factorial and Multiple(C++)

問題概要

問題文

$2$以上の正の整数$K$が与えられる。
正の整数$N$であって、$N!$が$K$の倍数になるようなもののうち最小のものを求めよ。
なお、このような$N$が存在することは証明できる。

制約

• $2\leq K\leq 10^{12}$

メモ

考えたこと

• まず、$K$がでっかいから$O(K)$とかは無理。かといって、$O(1)$で求まりそうにもない...
• テストケースを見ると、探索範囲も広そう...
• 単調性があるので、二分探索ベースかなぁ...
• 答えは最大でも$K$だから、探索範囲もわかる($\because K!=K\times\cdots\times1$より、$K!$は$K$の倍数)
• $N!$が$K$の倍数というところを高速に処理できれば...

解法

上にも書いた通り、二分探索で解ける。というのは、次が成り立つから

• ある$n$に対して、$n!$が$K$の倍数であったとする。この時、任意の$m>n$に対して$m!$は$K$の倍数

これは、$m!=m\times(m-1)\times\cdots\times n\times (n-1)\times\cdots\times1=m\times\cdots\times(n+1)\times n!$から導かれる。

要するに、ある境界を超えると、先はずっと条件を満たしてくれる。そして、その境界が答え!!!

$n!$が$K$の倍数であるという条件は次の条件と同値。以下、$K$の素因数分解を$K=\prod{p_i^{e_i}}$とする。

任意の$i$に対して次が成り立つ:

• $n!$を素因数分解したとき、$p_i$の指数は$e_i$以上

ここで、ルジャンドルの定理を使う。ルジャンドルの定理とは以下のようなもの。

正の整数$n$に対して、$n!$を素因数分解したとき、素数$p$の指数は

$$\sum_{e=1}^{\infty}{\left[ \frac{n}{p^e} \right]}$$

である

級数で書かれていますが、実際には途中の項からは$0$が続きます。なので、$0$が出てきた瞬間に打ち切って構いません。

詳しいことは、こちら
これを使うと、条件は

任意の$i$に対して次が成り立つ:

• $$\sum_{j=1}^{\infty}{\left[ \frac{n}{p_i^j} \right]}\geq e_i$$

となる。

• $i$の取りうる範囲:素因数の種類数に等しい。多く見積もっても$O(\log K)$
• $j$の取りうる範囲:$O(\log n)$

したがって、$O(\log K\log n)$で判定が行える。

実装例

• 素因数分解に$O(\sqrt K)$
• 二分探索で$O(\log K)$
• • 判定に$O(\log K\log n)$

素因数分解のところがボトルネックになり、全体では$O(\sqrt{K})$ぐらい。

#include<iostream>
#include<vector>
using namespace std;
using ll=long long;
//素因数分解
vector<pair<ll,ll>> prime_factorization(ll n){
    vector<pair<ll,ll>> res;
    for(ll p=2;p*p<=n;p++){
        if(n%p!=0)continue;
        ll e=0;
        while(n%p==0){
            e++;
            n/=p;
        }
        res.emplace_back(p,e);
    }
    if(n!=1)res.emplace_back(n,1);      //素数の場合
    return res;
}
int main(){
    ll k;
    cin>>k;
    auto fact=prime_factorization(k);
    //n!がkの倍数か?
    auto is_ok=[&](ll n)-> bool {
        for(auto pf:fact){
            ll p=pf.first;
            ll e=pf.second;

            ll e2=0;   //n!を素因数分解したときのpの指数
            ll pow=p;
            while(n/pow!=0){
                e2+=n/pow;
                pow*=p;
            }
            if(e>e2)return false;   //eのほうが大きかったらfalse
        }
        //全部クリアしたらtrue
        return true;
    };
    //二分探索
    ll ok=k;    //k!はkの倍数
    ll ng=0;    //0!=1は、kの倍数にはなり得ない
    while(abs(ng-ok)>1){
        ll mid=ng+(ok-ng)/2;
        
        if(is_ok(mid))ok=mid;
        else ng=mid;
    }
    cout<<ok<<endl;
}

• AC(18ms):https://atcoder.jp/contests/abc280/submissions/37717808