結果

問題 No.473 和と積の和
ユーザー lam6er
提出日時 2025-03-20 20:42:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 243 ms / 3,000 ms
コード長 1,380 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 85,444 KB
最終ジャッジ日時 2025-03-20 20:43:01
合計ジャッジ時間 5,414 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from functools import lru_cache

sys.setrecursionlimit(1 << 25)

def integer_nth_root(x, n):
    if x == 0:
        return 0
    low, high, best = 1, x, 0
    while low <= high:
        mid = (low + high) // 2
        try:
            val = mid ** n
        except OverflowError:
            high = mid - 1
            continue
        if val == x:
            return mid
        elif val < x:
            best = mid
            low = mid + 1
        else:
            high = mid - 1
    return best

def get_factors(n):
    factors = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            factors.add(i)
            factors.add(n // i)
        i += 1
    return sorted(factors)

@lru_cache(maxsize=None)
def count(current_product, k, min_factor):
    if k == 1:
        return 1 if current_product >= min_factor else 0
    max_d = integer_nth_root(current_product, k)
    lower = max(min_factor, 2)
    if lower > max_d:
        return 0
    factors = get_factors(current_product)
    res = 0
    for d in factors:
        if d > max_d:
            break
        if d < lower:
            continue
        if current_product % d != 0:
            continue
        res += count(current_product // d, k - 1, d)
    return res

n, x = map(int, input().split())
y = x + 1
required_min = 2 ** n
print(0 if y < required_min else count(y, n, 2))
0