結果
問題 | No.2016 Countdown Divisors |
ユーザー |
![]() |
提出日時 | 2022-07-22 21:52:44 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,282 bytes |
コンパイル時間 | 94 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-07-04 06:07:12 |
合計ジャッジ時間 | 3,776 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 RE * 15 |
ソースコード
class PrimeNumbers:def __init__(self, nmax):from math import isqrtrootnmax = isqrt(nmax)self.prime_judgement = [True]*(rootnmax+1)self.prime_judgement[0] = self.prime_judgement[1] = Falsefor i in range(2, rootnmax+1):if self.prime_judgement[i]:for j in range(2, rootnmax//i+1):self.prime_judgement[i*j] = Falseself.prime_list = []for i, flag in enumerate(self.prime_judgement):if flag: self.prime_list.append(i)def prime_factorization(self, n):return_list = []for i in self.prime_list:if n == 1 or i*i > n: breakif n%i == 0:return_list.append([i, 0])while n%i == 0: return_list[-1][1] += 1; n //= iif n != 1: return_list.append([n, 1])return return_listdef number_of_divisors(self, n):num = 1for _, v in self.prime_factorization(n): num *= v+1return numfrom sys import setrecursionlimitfrom functools import lru_cachesetrecursionlimit(10**6)@lru_cache()def main(n):m = n-pn.number_of_divisors(n)return main(m) if m else npn = PrimeNumbers(10**9)for _ in range(int(input())): print(main(int(input())))