回分類題庫
z048: C. 新 3N+1
關鍵字: 2014 NPSC 國中組初試

測資點 : 1 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 24 Times / 18 Users | Submit : 89 Times / 31 Users | Accepted rate : 58%
題目加入時間 : 2018-11-14 16:15

Content: 简体中文

寧寧是個對程式極有興趣的國中。有天,當她在網路上悠遊時看到了個令她覺得神奇的問題: 3N+1問題。

3N+1問題是這樣的:給個正整數N,如果它現在是偶數就除以,否則乘以三加,重複 直做下去,問你要做幾步才會變成

寧寧雖然覺得不可思議,也質疑是否所有的數字到最後都會變成,但聰穎的她仍很快的解出了這題。然⽽⾝個精益求精的好學,她並不滿於此。「題規定只能乘以三加,那如 果改成乘以AB會怎麼樣呢?」寧寧問著⾃⼰

為了挑戰⾃⼰的智慧,她定義了新·3N+1問題:給個正整數N,請找到最佳的正整數A,B 使得將原問題中的乘以三加換成乘以AB後數字最快變成

不幸的,這個問題變得太難,以於寧寧無法快速解出來。你有辦法幫助她嗎? 

Input:

 

輸⼊的第⼀⾏有⼀個正整數T,代表測試資料的筆數。

每⼀筆測試資料包含⼀個正整數N,代表新·3N+1問題中給定的N

• T 300000

• N 109


 

Output:

對於每筆測試資料請輸出⼀⾏,包含兩個最佳的正整數A,B

若有多組解,請輸出A的。若仍有多組,請輸出B的。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
4
5

Sample Output :

1 1
1 3

Hint :

個正整數N,如果它現在是偶數就除以 
 
範例說明

• 第⼀筆範例中,不論A,B是多少,N都會⼀直除以⼆,故直接輸出最⼩的A,B即可。
• 第⼆筆範例中,最短的過程為5 → 8 → 4 → 2 → 1。

Author :

2014 NPSC 國中組初試 (管理員:Chang)

  Solve it!   Status Forum