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…

O(√N) Ver // 素因数分解 // その素因数が何個あるかのmapを返す map<ll, ll> factorize(ll n){ map<ll, ll> mp; ll sq = sqrt(n); FOR(i, 2, sq+1){ while(n%i==0){ mp[i]++; n/=i; } } // 残り if(n!=1){ mp[n]++; } return mp; } // 約数の種類数 // 6 => 1, 2, 3, 6なの</ll,></ll,>…