PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[討論] Q10083: Division

看板Prob_Solve (計算數學 Problem Solving)作者tomas0011 (tomas0011)時間16年前 (2008/11/26 16:44)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/2 (看更多)

Q10083: Division (20點) 這題我有ＰＯ到知識家上： http://tw.knowledge.yahoo.com/question/question?qid=1508112308491 給你3個正整數 t,a,b（0 < t,a,b <= 2147483647），請你計算 ( t^a - 1) / (t^b - 1)。如果答案是小於100位數的整數，請輸出答案。否則請輸出 "is not an integer with less than 100 digits."。 Input 每組測試資料一列，含有3個正整數 t、a、b。 Output 每組測試資料輸出一列，如題目所述，格式請參考Sample Output。 Sample Input 2 9 3 2 3 2 21 42 7 123 911 1 Sample Output (2^9-1)/(2^3-1) 73 (2^3-1)/(2^2-1) is not an integer with less than 100 digits. (21^42-1)/(21^7-1) 18952884496956715554550978627384117011154680106 (123^911-1)/(123^1-1) is not an integer with less than 100 digits. --------------------------------------------------------------------------------------- 這題的重點是再,除數也就是分母也大於可以直接除的範圍假設一個很大的被除數跟小小的除數例如: 123123123123123123/123456 可以分割成 (123/123456)x 100000000000000 + (123/123456) x 1000000000000 ...... 可是這題的分母與分子都大餘可以用內建程式除的上限可能這題有一些技巧因為他是 (t^a-1) / (t^b-1) 若a=2的話平方公式就是 (t+1)(t-1) = (t^2-1) Q1:那無限呢? 若題目是輸入除數和被除數都非常大 (這只是假設) 被除數 120000000000000 除數 1200000000 被除數可以拆成 (1200/1200)x(1000/1000)x(1000/1000)x1000x100 若被除數 21569874135145679246568947894654....... 除數 5645123487896456489421321.... 這種找因式的方法可能就跑不出來了而一直相減的暴力法就更不用說了... (大數相除 *除數和被除數都溢位) Q2:不知道有大大有什麼好方法可以提供^^???? (VB6.0程式碼或者演算法都OK=ˇ=") -分割線--剛剛自己想出來的方法--------------------------- 用相乘and相減找個位數這三個重點破解一組答案先新增一個空白s="" (這是一組小算盤可以計算的數字) 假設 t^a-1=304696744428557889118768=a t^b-1=4654954984844849=b 兩個相除的結果=65456432=c 至於怎麼推到答案 a/b = c = 65456432 首先看尾數 b的尾數=9 9*多少=a的尾數8 對乘2=18 把a-b整項*2 304696744428557889118768 - 4654954984844849*2 ------------------------- 304696735118647919429070 因為已經求到一位 2 所以把 0消掉(消掉一位) 304696735118647919429070/10 此時 a =30469673511864791942907 s= 2 & s 繼續 b的尾數=9 9*多少=a的尾數7 對乘3=27 把a-b整項*3 30469673511864791942907 - 4654954984844849*3 ------------------------ 30469659546999837408360 求到一位 3 所以把 0 消掉 a又變成了 3046965954699983740836 此時 s= 3 & s s 內容 = 32 以此類推最後結果可以推到65456432 ＜使用程式ＶＢ６＞不知道有沒有其他更好更快速的解法？或是　這題的正統解法？？ -- ※性別：男　 ※生日：1990/05/08 ※星座：金牛座　 ※血型：Ａ　 ※我的無名；http://www.wretch.cc/blog/tomas0011 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.130.37.170