d472: 算術基本原理
Tags : mod 分治法
Accepted rate : 93人/100人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-10-12 17:26

Content
好多年前,希臘有一個叫 Euclid  的數學家發現了在正整數的集合裡質數的個數是有無窮多。在他的著名的著作《幾何原本》裡,他證明了算術基本原理:

對於任何一個自然數 N ,必能找到一個唯一的正整數序列 k 滿足以下等式(我們定義 Pi 為第 i個質數,p1=2 ):
 

 
今天你的任務很簡單,並不需要去證明此原理。而是給定 k 序列( k 僅列出至最後一個非零項 ),然後求出所表示的 N ,由於 N 可能會很大,請輸出 N mod 76543。

Input

 第1行至第L行:第 i 行的一個正整數 n 表示 ki,1≦n≦10000,1≦L≦1000。

Output

第1行:一個正整數 n 表示相對應k序列的 N mod 76543

Sample Input #1
31
5
6
7
9
Sample Output #1
64239
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (20%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (30%): 1.0s , <1M
不公開 測資點#3 (40%): 1.0s , <1M
Hint :

Mod 運算的特性

Tags:
mod 分治法
出處:
Zetadavid [管理者:
pscd (PSCD)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」