Re: [VB6 ] Q10083: Division

[gofin (雲色)]

我不知道我的想法有沒有問題!但是提出來大家參考一下
如果有錯也請不吝指教

先把算式拆成兩半
分母: (t^b -1)
    = (t^b-t^0) 因當t越大 t^0越不重要
    = 假設分母為t^b
分子: (t^a -1)
    =同上理
    =假設分子為t^a

還原:t^a/t^b=t^(a-b)

然後用t^(a-b)去找出小於一百位數的整數應該會比原本公式簡單
(當然應該也會用到大數相乘或相加的函數..網路上很多..可求google大神)

找出這些整數後 再全部丟回原本的公式 檢查是否為整數...

這樣應該會比較快....?

※ 引述《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=ˇ=")

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.130.143.182
推 tomas0011:嗯！！ 大數相乘,次方ok 重點還是在相除^^"
→ tomas0011:分子跟分母都超出上限  呵 剛題目我有一點地方看錯
→ tomas0011:如果 分子除分母為整數也就是整除！分母則為分子的因數
→ tomas0011:問題就來了！要如何把分母（大數）分割 成較小的因數
→ tomas0011:而每次除分母因數時判斷分子是否變為小數 即為不整除^^?
→ tomas0011:可是若途中遇到了超過可以用 "除法直接除的(分母)質數"
→ tomas0011:題目又會產生bug囉 ！！   好難ˊˋˊˋˊˋˊˋ