Submission #15,189

2025-02-16 00:59:48

pypy3

Accepted 100/100

876ms

68272 KiB

import sys
input=sys.stdin.readline
D={1:1, 2:1, 3:1, 4:1}
F=[1,2]
while F[-1]+F[-2]<10**9:
 F.append(F[-1]+F[-2])

def S(M):
 if M in D:
  return D[M]
 r=0
 for i in range(1,43):
  if M%F[i]==0:
   r+=S(M//F[i])
 D[M]=r
 return r

for test in range(1,int(input())+1):
 M=int(input())
 sys.stdout.write(str(S(M))+'\n')

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	41ms	19436 KiB
		2	Accepted	61ms	21740 KiB
subtask2	25/25
		3	Accepted	52ms	21656 KiB
		4	Accepted	64ms	21716 KiB
		5	Accepted	59ms	21552 KiB
		6	Accepted	54ms	21504 KiB
subtask3	25/25
		7	Accepted	59ms	21660 KiB
		8	Accepted	75ms	22432 KiB
		9	Accepted	59ms	21912 KiB
		10	Accepted	52ms	21556 KiB
subtask4	25/25
		11	Accepted	423ms	50304 KiB
		12	Accepted	407ms	53744 KiB
subtask5	25/25
		13	Accepted	808ms	64900 KiB
		14	Accepted	876ms	68272 KiB