c053: 3. 蛋餅愛質數
標籤 :
通過比率 : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2025-05-17 17:26

內容

蛋餅有 N 個數字 a1, a2, ..., aN,這些數字兩兩相異。因為蛋餅很喜歡質數,他想要從這裡⾯挑選⼀些數字使兩兩相異數字的總和都是質數,你能幫幫他計算總共有幾種⽅法嗎?

更明確的說,請計算有幾個序列 b1, b2, ..., bK 滿⾜:

  • 1 ≤ b1 < b2 < b3 < ... < bK ≤ N
  • 對於所有 1 ≤ i < j ≤ K,abi + abj 是質數
輸入說明

輸入第⼀⾏有⼀個正整數 N,代表數字的數量。

輸入第⼆⾏有 N 個正整數 a1, a2, ..., aN,ai 代表第 i 個數字為何。

  • 2 ≤ N ≤ 60
  • 1 ≤ ai ≤ 1000
  • ai ≠ aj∀1 ≤ i < j ≤ N
輸出說明

請輸出⼀個整數,代表有幾種序列滿⾜條件。保證在資料範圍的限制下,答案會在 64 bit 整數範圍內。

範例輸入 #1
3
3 1 4
範例輸出 #1
5
範例輸入 #2
5
2 4 6 8 10
範例輸出 #2
5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
提示 :

在第⼀筆範例測資中,總共有以下五種可能的選法:

  • [3]
  • [1]
  • [4]
  • [3, 4]
  • [1, 4]
標籤:
出處:
2024YTP決賽 [管理者:
zero (管理員)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」