結果

問題 No.1463 Hungry Kanten
コンテスト
ユーザー LyricalMaestro
提出日時 2025-03-28 23:33:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,117 ms / 2,000 ms
コード長 2,041 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 226,428 KB
最終ジャッジ日時 2025-06-20 02:28:51
合計ジャッジ時間 5,636 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/737

import math

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    # aの素因子として含まれる素数の列挙
    prime_set = set()
    for a in A:
        sqrt_a = int(math.sqrt(a))
        for p in range(2, sqrt_a + 1):
            if a % p == 0:
                while a % p == 0:
                    a //= p
                prime_set.add(p)
        if a > 1:
            prime_set.add(a)
    
    base_primes = list(prime_set)
    base_primes.sort()

    # a をベクトル化してみる
    vec_a = []
    for a in A:
        base_array = [0] * len(base_primes)
        for i, p in enumerate(base_primes):
            if a % p == 0:
                cnt = 0
                while a % p == 0:
                    cnt += 1
                    a //= p
                base_array[i] = cnt
        vec_a.append(tuple(base_array))
    
    # 総積の組み合わせ
    answer_set = set()
    for bit in range(2 ** N):
        k = 0
        for i in range(N):
            if bit & (1 << i) > 0:
                k += 1

        if k < K:
            continue

        answer_vec = [0] * len(base_primes)
        for i in range(N):
            if bit & (1 << i) > 0:
                for j in range(len(base_primes)):
                    answer_vec[j] += vec_a[i][j]
        answer_set.add(tuple(answer_vec))

    # 総和の組み合わせ
    for bit in range(2 ** N):
        k = 0
        ans = 0
        for i in range(N):
            if bit & (1 << i) > 0:
                k += 1
                ans += A[i]
        if k < K:
            continue

        vec = [0] * len(base_primes)
        for j, p in enumerate(base_primes):
            cnt = 0
            while ans % p == 0:
                ans //= p
                cnt += 1
            vec[j] = cnt
        if ans > 1:
            vec.append(ans)
        vec = tuple(vec)
        answer_set.add(vec)
    print(len(answer_set))



            
    





if __name__ == "__main__":
    main()
0