結果

問題 No.2798 Multiple Chain
ユーザー shobonvipshobonvip
提出日時 2024-06-27 00:01:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 1,716 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 81,908 KB
実行使用メモリ 66,192 KB
最終ジャッジ日時 2024-06-27 00:01:18
合計ジャッジ時間 4,462 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
62,588 KB
testcase_01 AC 47 ms
61,188 KB
testcase_02 AC 45 ms
62,264 KB
testcase_03 AC 45 ms
60,912 KB
testcase_04 AC 49 ms
62,156 KB
testcase_05 AC 47 ms
61,992 KB
testcase_06 AC 50 ms
61,144 KB
testcase_07 AC 49 ms
62,028 KB
testcase_08 AC 50 ms
62,096 KB
testcase_09 AC 53 ms
62,412 KB
testcase_10 AC 49 ms
62,096 KB
testcase_11 AC 50 ms
61,916 KB
testcase_12 AC 54 ms
62,808 KB
testcase_13 AC 51 ms
61,256 KB
testcase_14 AC 50 ms
62,120 KB
testcase_15 AC 49 ms
62,604 KB
testcase_16 AC 50 ms
61,036 KB
testcase_17 AC 48 ms
61,660 KB
testcase_18 AC 47 ms
61,380 KB
testcase_19 AC 48 ms
61,824 KB
testcase_20 AC 46 ms
62,004 KB
testcase_21 AC 46 ms
61,232 KB
testcase_22 AC 46 ms
61,468 KB
testcase_23 AC 46 ms
61,260 KB
testcase_24 AC 46 ms
62,560 KB
testcase_25 AC 45 ms
61,236 KB
testcase_26 AC 47 ms
61,920 KB
testcase_27 AC 45 ms
61,524 KB
testcase_28 AC 46 ms
61,380 KB
testcase_29 AC 46 ms
61,348 KB
testcase_30 AC 47 ms
61,892 KB
testcase_31 AC 54 ms
62,392 KB
testcase_32 AC 56 ms
65,756 KB
testcase_33 AC 50 ms
63,200 KB
testcase_34 AC 65 ms
66,192 KB
testcase_35 AC 47 ms
61,576 KB
testcase_36 AC 47 ms
61,636 KB
testcase_37 AC 45 ms
61,456 KB
testcase_38 AC 47 ms
63,492 KB
testcase_39 AC 46 ms
63,084 KB
testcase_40 AC 45 ms
62,420 KB
testcase_41 AC 46 ms
61,372 KB
testcase_42 AC 45 ms
61,920 KB
testcase_43 AC 45 ms
62,924 KB
testcase_44 AC 46 ms
62,740 KB
testcase_45 AC 45 ms
61,200 KB
testcase_46 AC 45 ms
62,264 KB
testcase_47 AC 46 ms
62,836 KB
testcase_48 AC 47 ms
62,272 KB
testcase_49 AC 57 ms
63,228 KB
testcase_50 AC 46 ms
61,264 KB
testcase_51 AC 46 ms
62,564 KB
testcase_52 AC 53 ms
64,344 KB
testcase_53 AC 46 ms
61,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://judge.yosupo.jp/submission/90854
import random

def gcd(a, b):
	while a: a, b = b%a, a
	return b

def isprime(n):
	if n == 2: return 1
	if n == 1 or n%2 == 0: return 0
	m = n-1; lsb = m & -m; s = lsb.bit_length()-1; d = m//lsb
	if n < 4759123141: test_numbers = [2, 7, 61]
	elif n < 341550071728321: test_numbers = [2, 3, 5, 7, 11, 13, 17]
	elif n < 3825123056546413051: test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	else: test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	for a in test_numbers:
		if a == n:continue
		x = pow(a,d,n); r = 0
		if x == 1:continue
		while x != m:
			x = pow(x,2,n); r += 1
			if x == 1 or r == s:return 0
	return 1

def find_prime_factor(n):
	m = max(1,int(n**0.125))
	while True:
		c = random.randrange(n); y = k = 0; g = q = r = 1
		while g == 1:
			x = y; mr = 3*r//4
			while k < mr: y = (pow(y,2,n)+c)%n; k += 1
			while k < r and g == 1:
				ys = y
				for _ in range(min(m, r-k)): y = (pow(y,2,n)+c)%n; q = q*abs(x-y)%n
				g = gcd(q,n); k += m
			k = r; r <<= 1
		if g == n:
			g = 1; y = ys
			while g == 1: y = (pow(y,2,n)+c)%n; g = gcd(abs(x-y),n)
		if g == n:continue
		if isprime(g):return g
		elif isprime(n//g):return n//g
		else:return find_prime_factor(g)

def factorize(n):
	res = {}
	for p in range(2,1000):
		if p*p > n: break
		if n%p: continue
		s = 0
		while n%p == 0: n //= p; s += 1
		res[p] = s
	while not isprime(n) and n > 1:
		p = find_prime_factor(n); s = 0
		while n%p == 0: n //= p; s += 1
		res[p] = s
	if n > 1: res[n] = 1
	return res

n = int(input())
d = factorize(n)
b = [0] * 61
b[0] = 1
for i in range(1, 61):
	for j in range(0, 61):
		if j-i >= 0:
			b[j] += b[j-i]

ans = 1
for i, c in d.items():
	ans *= b[c]
print(ans)
0