約数列挙について
- テンプレートになっている
10^12ぐらいまで行ける- divisorとは約数のこと
約数列挙のpythonによる実装例
def make_divisors(n):
divs = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divs.append(i)
if i != n // i:
divs.append(n//i)
divs.sort()
return divs
(約数列挙の応用)N以下のすべての約数を素因数分解する
エラトステネスの櫛のロジックを変更することで列挙を行うような素因数分解を高速に行うことができる
mport 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]), (11, [11]), (12, [2, 3]), (13, [13]), (14, [2, 7]), ...
例; 約数が解の候補になる例
問題
AtCoder Beginner Contest 190; D - Staircase Sequences
解答
N=int(input())
def make_divisors(n):
divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
divisors.sort()
return divisors
# 奇数の約数が解の候補になる
# 対象性があるので二倍する
divs = make_divisors(N)
cnt = 0
for div in divs:
if div%2 != 0:
cnt += 2
print(cnt)
例; 約数が解の十分条件になっている例
問題
diverta 2019 Programming Contest; D - DivRem Number
解答
# floor(N/m) = N%m
# これは、 N = k*m + k -> N = k(m+1)
# となり約数の問題にすることができる
N=int(input())
def make_divisors(n):
divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
divisors.sort()
return divisors
divs = make_divisors(N)
acc = 0
for div in divs:
if div > 1 and N//(div-1)==N%(div-1):
acc+=div-1
print(acc)