例; 約数の個数を求める
問題
AtCoder Beginner Contest 052; C - Factors of Factorial
解説
素因数分解をしS=p1^n1*p2^n2*...という結果が得られたとき、約数の個数は(n1+1)*(n2+1)*...である
解答
素数列挙について
- エラトステネスの篩でできる
- やっていることはdpを使っての計算量削減
def sieve(n):
dp = [1]*(n+1) # 初期値ですべてを素数と仮定
dp[0] = 0; dp[1] = 0
for i in range(2, n+1):
if dp[i]: # もし素数ならば
j = 2 * i # iの倍数はすべて素数ではないはず
while j <= n:
dp[j] = 0
j += i
return [i for i in range(n) if dp[i]]
Nまでの数字のすべての数の素因数分解を行う
import collections
import math
def sieve_div(n):
dp = [1]*(n+1) # 初期値ですべてを素数と仮定
dp[0] = 0; dp[1] = 0
divs = collections.defaultdict(list)
for i in range(2, n+1):
if dp[i]: # もし素数ならば
divs[i].append(i)
j = 2 * i # iの倍数はすべて素数ではないはず
while j <= n:
dp[j] = 0
divs[j].append( i )
j += i
return divs
print(sorted(sieve_div(100).items())) # [(2, [2]), (3, [3]), (4, [2]), (5, [5]), (6, [2, 3]), (7, [7]), (8, [2]), (9, [3]), (10, [2, 5]), ...
例題
例; エラトステネスの篩の応用(お互いに割り切れない数を求める)
問題
AtCoder Beginner Contest 170; D - Not Divisible
解説
やり方はエラトステネスの篩の櫛と同じであるが素数でないのでそこまで最適化されない
dpっぽいテーブルを使って解くことで解くことができる
説明
def sieve(arr):
max_ = max(arr)
is_baisu = [0 for _ in range(max_+1)]
for a in arr:
is_baisu[a] += 1
for b in range(a*2, max_+1, a):
is_baisu[b] += 1
cnt = 0
for a in arr:
# is_baisu[a] == 1であることは、一度しかその変数で作られておらず、他の数の倍数で表現できないということ
if is_baisu[a] == 1:
cnt += 1
print(cnt)
N=input()
A=list(map(int,input().split()))
sieve(A)
例; gcdに関連する問題
問題
解説
- エラトステネスの櫛を使うのは理解できる
- gcd(A, B) == Aとなってしまう要素を消さなくてはいけないのであるが、除法定理を用いて計算するところが非常に難しい
- gcd(A, B) == Aとなるのは素因数の数が偶数の時である
解答
import collections
L, R = map(int,input().split())
def sieve():
n = R
dp = [1]*(n+1) # 初期値ですべてを素数と仮定
dp[0] = 0;
dp[1] = 0
nex = collections.defaultdict(int)
for i in range(2, n+1):
if dp[i]: # もし素数ならば
nex[i] += 1
j = 2 * i # iの倍数はすべて素数ではないはず
while j <= n:
dp[j] = 0
nex[j] += 1
j += i
j = i*i
while j <= n:
nex[j] = -10**9 - 7
j += i*i
return nex
nex = sieve()
ans = 0
for i in range(2, R+1):
if nex[i] < 0:
continue
cc = R//i - (L-1)//i # その数の倍数の個数
if nex[i]%2 == 1: # 共通の素因数にならない個数(= 奇数の素因数の組み合わせ - 偶数の素因数の組み合わせ
ans += (cc*(cc-1))//2
else:
ans -= (cc*(cc-1))//2
for i in range(max(2, L), R+1): # わかりやすい倍数を消去
ans -= R//i - 1
print(ans*2)