📖

ABC280 D - Factorial and Multiple(C++)

2023/01/03に公開約2,500字

問題概要

問題文

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]}

である

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

任意の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;
}

Discussion

ログインするとコメントできます