2013年7月23日 星期二

1195 - Calling Extraterrestrial Intelligence Again

在 1974 年,11 月 16 日星期六中午,有一則由人類撰寫的訊息經由 波多黎各 的 阿雷西博天文台 傳送給外星生命,這則訊息由 1679 bits 構成,將轉換成 23 x 73 矩形的圖示。由於 23 和 73分別都是質數,因此圖形將只會有一種轉換可能,但不保證接收到的外星生命會將此進行轉換,就算會進行轉換也有可能不正確,阿雷西博天文台的發送者非常樂觀看待。



我們也有一個非常類似的計畫,你的任務要找到最合適的長和寬來轉換圖片,而什麼是"最合適"定義如下:

對於一個整數 m  > 4,而有一個分數 a/b <= 1,而圖片面積不超過 m,而且長寬都必須要是質數,且寬長比不可小於 a/b,也不可大於 1,要最大化圖片面積。


換個方式說,給定一個整數 m,以及分數 a/b,其中 m > 4, 0 < a/b <= 1,找到一組質數 p, q 符合 pq <= m, a/b <= p/q <= 1, p*q 越大越好,輸出一組 p, q

Input 

輸入測資不超過 2000 筆,最後一行以 0 0 0 結束。


每組測資有三個整數 m, a, b ( 4 < m <= 1000001 <= a <= b <= 1000 )

Output 

對於每組測資,輸出一對整數,分別對應 p, q

Sample Input 

5 1 2
99999 999 999
1680 5 16
1970 1 1
2002 4 11
0 0 0

Sample Output 

2 2
313 313
23 73
43 43
37 53

沒有留言:

張貼留言