2019-03-29から1日間の記事一覧

エラトステネスのふるい

const int N_MAX = 10010; bool is_prime[N_MAX]; // エラトステネスのふるい void Eratosthenes(){ FOR(i, 0, N_MAX){ is_prime[i] = true; } is_prime[0] = false; is_prime[1] = false; FOR(i, 2, N_MAX){ if(is_prime[i]==1){ int p = i; int step_p = p…

素因数分解, 約数の種類数, 高速版 osa_k ~高速な素因数分解~

// 素因数分解 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) // 素因数分解 /</ll,></ll,>…