Участник:ZhenyaStrelkova/DIVSUM

Материал из DISCOPAL
< Участник:ZhenyaStrelkova
Версия от 20:48, 22 ноября 2020; ZhenyaStrelkova (обсуждение | вклад) (Новая страница: «https://www.spoj.com/problems/DIVSUM/ <code-python> max_val = 500005 sigma = [0] * max_val least_prime = [0] * max_val prime = [0] * max_val pc = [0] * max_val…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://www.spoj.com/problems/DIVSUM/

max_val = 500005
sigma = [0] * max_val
least_prime = [0] * max_val
prime = [0] * max_val
pc = [0] * max_val
 
for i in range(2, max_val):
    if least_prime[i] == 0:
        for j in range(i, max_val, i):
            if least_prime[j] == 0:
                least_prime[j] = i
 
sigma[1] = 1
for i in range(2, max_val):
    j = i // least_prime[i]
    if j % least_prime[i] == 0:
        prime[i] = prime[j]
        pc[i] = pc[j] * least_prime[i]
    else:
        prime[i] = j
        pc[i] = least_prime[i]
    sigma[i] = sigma[prime[i]] * (pc[i] * least_prime[i] - 1) // (least_prime[i] - 1)
T = int(input())
for _ in range(T):
    N = int(input())
    print(sigma[N] - N)