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