[VB6 ] Q10083: Division

[tomas0011 (tomas0011)]

有高手可以幫解題嗎^^?（這不是作業）

我有貼在知識家：
http://tw.knowledge.yahoo.com/question/question?qid=1508112308491

內容：

Q10083: Division (20點)

給你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=ˇ=")

--
     ※性別：男　
     ※生日：1990/05/08
     ※星座：金牛座　
     ※血型：Ａ　
     ※我的無名；http://www.wretch.cc/blog/tomas0011

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.130.37.170
→ MOONRAKER:不是作業那麼更不需要別人幫你解，自己解出來才是自己的
→ MOONRAKER:自己implement一套計算大整數的方法比較實在
→ MOONRAKER:用陣列存各個位數
→ tomas0011:我這題想要知道　正統解法耶　＝　＝｜想怪怪的解法很累
→ tomas0011:而且效率又不一定很好ˊˋ～
→ tomas0011:而且我上面有提供自己的解法　覺得"效率"不是很好～
→ tomas0011:其實我這題也是幫人問的～0.0~
→ tomas0011:用陣列儲存各個位數　好像是用再大數相乘　這是除ｘｄｄ
→ MOONRAKER:你以為大數不能寫除法啊？
→ tomas0011:可以 Big mod Big 除 都可以 但是 如果除數大於上限
→ tomas0011:也就是分母！！ 大於上限的話！！～
→ tomas0011:就是這題的重點了^^"~