読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

SRM 643 Div1 Easy - TheKingsFactorization

問題

TopCoder Statistics - Problem Statement

問題概要

自然数N素因数分解を求めよ。ただし、Nの素因数の小さい方から順に奇数番目だけ素因数が何であるかのヒントが与えられる。

例えば、N=60であるとき、素因数分解60 = 2 * 2 * 3 * 5であるから、小さい方から数えて奇数番目の2 , 3がヒントとして与えられる。

  •  2 \le N \le 10^{18}

イデア

普通に素因数分解するのでは、O(\sqrt{N})かかってしまうので、間に合わない。そこで、ヒントを利用する。

まず、ヒントとして与えられる素因数の個数で、全体の素因数が何個あるかの見当を付けることが出来る。例えば、ヒントが2個なら、答えには3個か4個の素因数があるはずである。

ヒントの個数が1個なら、答えに含まれる素因数の個数は1個か2個ということになる。これはヒントをみればどちらになるか簡単に判断できて、その1個がNと一致するなら素因数は1個で、そうでないならNをそのヒントで割った値も素因数になっていることが確定する。

以下、ヒントの個数が2個以上である状況を考える。まず、Nを既にわかっている素因数で割っておく。

まず、素因数分解の素朴な方法として、最初に述べた計算量からも推測がつく通りNに対する素因数分解2から\sqrt{N}までのそれぞれで割れるかどうかを試すという方法がある。それぞれの数で順番にNを割っていき、終わった時点でNが1よりも大きければその数も(\sqrt{N}より大きい)素因数であるといえる。

これだけだと間に合わないが、ここでヒントを利用する。ヒントの中で一番大きい数pに注目する。すると、ヒントの与えられ方の性質から、p以上の素因数は多くとも1つしかないことが分かる。よって、Nを試し割りするのはこのp以下で十分である事がわかる。

pがとても大きい数だったらこの制約は意味がないじゃないかと思うかもしれないが、直感的にはpが大きいような状況では、既にNpで割られているので\sqrt{N}が十分小さくなるというイメージで計算が間に合う。

最悪の状況を考えてみると、実際に素因数が3個である状況を考え、与えられるヒントが2とpだったとする。この時に、2つの制約\sqrt{N}pがちょうど拮抗する状況を考えても、N \le 10^{18}であるから試し割りの範囲は最悪でも10^6くらいに収まることが分かる。

とても面白い問題だった。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

class TheKingsFactorization {
    public:
    vector<long long> getVector(long long N, vector<long long> primes) {
        vector<ll> ret(primes);
        int P = primes.size();

        rep(i,P) N/=primes[i];

        if(P==1)
        {
            if(N!=1) ret.pb(N);
            return ret;
        }

        ll t=N;
        int i=2;
        while(i*i<=N && i<=primes[P-1])
        {
            while(t%i==0)
            {
                t/=i;
                ret.pb(i);
            }

            ++i;
        }
        if(t>1) ret.pb(t);

        sort(all(ret));
        return ret;
    }
};