perogram

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=105あたりまでしか計算していなかったら1つWA
  • 2 * 105 + α くらいにかなり余裕を持たせて事前計算したらAC

タグづけ

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