Re: [VB6 ] Q10083: Division

[tomas0011 (tomas0011)]

※ 引述《gofin (雲色)》之銘言：
: → tomas0011:如果 分子除分母為整數也就是整除！分母則為分子的因數   11/25 22:57
: → tomas0011:問題就來了！要如何把分母（大數）分割 成較小的因數     11/25 22:58
: → tomas0011:而每次除分母因數時判斷分子是否變為小數 即為不整除^^?  11/25 22:59
: → tomas0011:可是若途中遇到了超過可以用 "除法直接除的(分母)質數"   11/25 23:01
: → tomas0011:題目又會產生bug囉 ！！   好難ˊˋˊˋˊˋˊˋ         11/25 23:01
: 續之前t^(a-b)找出可能的值
: 再把這些值丟進(t^a)-1/(t^b)-1
: 分別算出分子跟分母的數字(這裡可能需要大數相乘)
: 如果說有個函數是可以分解一個數字的因式
: EX:輸入25會輸出5^2 或輸入75會輸出5^2*3^1
: 這樣就把分子跟分母切開送進去.....
: 然後先比較
: if 分子的底數是否包含全部分母的底數
:       if 這些相同底數的分子指數都大於分母指數
:         如果有的話(應該就會整除) 就算一算輸出答案
:         (怎算就是 假設a,b都是分子跟分母都有的底數,c^e,d^f是分子多的
:         =a^(分子指數減分母指數)*b^(分子指數減分母指數)*c^e*d^f
:         P.S到這其實只是一串底數跟指數的組合,如果需要輸出確切的數字就用大數
:         相乘算出來吧,,,,但是我倒覺得算到這邊應該就差不多了!
:       else
:         分子指數減分母指數會等於負的
:         =沒辦法整除
:       end if
: else
:      =沒辦法整除
: end if
: 參考看看

用這個方法可能會牽扯到大數的因數分解

如果分解出來的那個數值又是大數（也就是無法在分割的質數）

又會碰上了相乘的問題


我想到了一個解法

(t^a-1)/(t^b-1)=答案

如果用交差相乘 則 (t^a-1)=(t^b-1)*答案

可能會變成單純的大數相乘 至於範圍

假設(t^a-1)長度為10
(t^b-1)長度為5

以最壞最壞的打算 假設
t^a-1=1000000000
t^b-1=10000

那迴圈的範圍就會落在長度6 長度7之間

也就是 100000-1000000 也許可能有bug

或是個增加一個範圍 長度5到8之間


至於判斷答案*（t^b-1) 是否為(t^a-1)

則可以用 t=split(t^b-1*答案,t^a-1)

若 ubound(t)=1 而且 t(0) and t(1) =empty

那答案為正解 若 迴圈跑完 還找不到答案

則為小數點

嗯！！可能效率還是很差



謝謝你讓我想到一個或許可行的解法～

------------分割限-----------------

來了

就我所說的發展一個可行的

用相乘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

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.130.37.170
→ tomas0011:還是很慢 只能判斷 個位數相乘的時候是不是最右邊的
→ tomas0011:是 (t^a-1)  最右邊 那位數  盡可能跳過不需要的位數0.0
推 gofin:因為沒有實際下去寫!所以不是很明確知道會錯在哪...
→ gofin:但是!我覺得因式分解應該是可以減少很多演算的步驟
→ gofin:至於大數因數分解可以去做一個質數陣列來處理
→ gofin:質數陣列 列出小於 2147483647即可(這質數表應該網路查的到)
→ tomas0011:剛上完英文課 腦袋一直想 我又想到方法了... 修改文章XD
※ 編輯: tomas0011       來自: 140.130.37.170       (11/26 15:47)
※ 編輯: tomas0011       來自: 140.130.37.170       (11/26 15:53)
推 gofin:但是這樣的前提是要能整除...
→ tomas0011:恩　這題　是要顯示能整除　且１００位以內
→ tomas0011:要顯示小數的話　　我不知道要怎麼破解了ˊˋ||
→ tomas0011:其實好像也可以　這個方法可以求到餘數
→ tomas0011:求到餘數之後　本來判斷尾數　改成判斷首數（以不超過
→ tomas0011:或者相等的成積)
→ tomas0011:來求小數
推 gofin:喔我的意思是說上面的範例是因為剛好可以整除所以好解..
→ tomas0011:對了我這題有PO在Prob_solve版 有人有解法"輾轉相除法"
推 gofin:嗯!好方法!我的是程式寫法!但是一樣都是求最大因數的
→ gofin:我那兩層if就是最大因數!!  用gcd的function也可以~
→ gofin:好久沒算數學都忘記還有gcd!!呵...PTT果然強者很多....