perogram

素因数分解

1114C - Trailing Loves (or L'oeufs?) 〜階乗に含まれる素因数の数〜

Quiz https://codeforces.com/contest/1114/problem/C AC Code https://codeforces.com/contest/1114/submission/56636163 観察 n!内にbがいくつ含まれるかが答え n, b共に値域が広く、O(N)では間に合わない ルジャンドルの定理 n! に含まれる素因数 p の数 …

D - DivRem Number 約数列挙 約数一覧

Quiz https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d Submit コンテスト中 https://atcoder.jp/contests/diverta2019/submissions/5361687 コンテスト後 整理ver https://atcoder.jp/contests/diverta2019/submissions/5369617 解法 8 = 3x2 …

素因数分解

// 素因数分解 map<ll, ll> factorize(ll n){ map<ll, ll> mp; FOR(i, 2, n+1){ while(n%i==0){ mp[i]++; n/=i; } } return mp; } シンプルにできたので保存 計算量O(N) 別VER 上のはn=1010などではTLE https://yukicoder.me/submissions/335272 計算量O(√N) map<ll, ll> factorize(l</ll,></ll,></ll,>…

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> fa</ll>…