D - Factorization abc110_d

Quiz

https://atcoder.jp/contests/abc110/tasks/abc110_d

Submit

https://atcoder.jp/contests/abc110/submissions/4246912

解法

• editorialや、けんちょんさんの記事と同じ

素因数分解

• 過去の提出から再利用
• 因数に1が含まれないように微修正した

vector<ll> factorization(ll N){
    ll n = N;
    vector<ll> A;
    ll sq = sqrt(n);
    FOR(i, 2, sq+1){
        while(n%i==0){
            n /= i;
            A.push_back(i);
        }
    }
    if(n!=1){
        A.push_back(n);    
    }
    return A;
}

ひっかかりポイント

• nCrにて、フェルマーの小定理を使うために事前計算するが、n=10⁵あたりまでしか計算していなかったら1つWA
• 2 * 10⁵ + α くらいにかなり余裕を持たせて事前計算したらAC

タグづけ

• 今回の記事から要素をタグづけするようにした
• するとタグからも辿れる
• いつもは検索バーから似た問題を探していたが、今後はそれが変わるかも