[回到版面]
回應模式
名 稱
內 文
附加圖檔[] []
  • 可附加圖檔類型:GIF, JPG, JPEG, PNG, WEBM,瀏覽器才能正常附加圖檔
  • 附加圖檔最大上傳資料量為 3072 KB。
  • 當檔案超過寬 125 像素、高 125 像素時會自動縮小尺寸顯示
  • 目前附加圖檔使用量大小: 207379 KB / 500000 KB
  • 回覆時程式碼縮排會被trim消掉,請善用[code][/code]標色或貼到ideone等網站
  • LaTeX記法可以用「$$」或「\( \)」包起來,例如「$\sum_{k=1}^{k=n} k^2 = \frac{n(n+1)(n+2)}{6}$」
  • 投稿時請點擊畫像認證後,再按下 [送出] 按鈕提交。
  • 鬧板、攻擊性發言、煽動性發言請無視(回應者也無視),並使用del或在貓管理部向管理員回報。
  • 新介面尚處於測試階段,如果有任何問題可以向管理員或於程設交流版反映。

檔名:1539538970997.png-(559 KB, 560x720)
559 KB
關於2的64次方無名18/10/15(一)01:42:50 ID:TiVLrbeMNo.12898del
請問有沒有什麼寫法或觀念能讓程式快速跑完2的64次方次呢?
最近碰到了一個題目,要求從1開始接到n再除以2018,求餘數
假如n是7,那麼就是1234567除以2018的餘數
2的64次方>n>0
無名18/10/15(一)01:43:33 ID:TiVLrbeMNo.12899del
檔名:1539539013906.png-(1560 KB, 800x1234)
1560 KB
獻上祭品
無名18/10/15(一)11:26:13 ID:tLFTnigQNo.12900del
首先給你看2的64次方要跑多久
https://www.youtube.com/watch?v=S9JGmA5_unY


這種題型的觀念通常是用同餘定理
(m+n)%c == (m%c+n%c)%c
(m*n)%c == ((m%c)*(n%c))%c
m^n%c == (m%c)^n%c
無名18/10/15(一)17:03:26 ID:CPr.4ouUNo.12901del
檔名:1539594206723.jpg-(332 KB, 1448x2048)
332 KB
>>12900
原來如此
是要用定理解,不能硬做啊

雖然很不好意思,但是還有個小問題
請問m是什麼數字?
無名18/10/15(一)22:17:16 ID:0cfdC2BoNo.12902del
>>12901
定理公式,n跟題目的n無關

這題怎麼解我也還沒想通
無名18/10/17(三)16:38:45 ID:zmy9Usb2No.12904del
文超長注意
如果你是個連程式基本語法都不很熟的新手,建議你直接跳過這題
或是去數學系找個比我還要簡潔百倍的解法
這題考的是數學不是程設
需要的是把一個超爆幹長的數學過程寫成程式


首先,依照位數不同把這個超爆幹大的數字切成20段
123456789
101112131415......979899
100101102103104......997998999
... ... ...
100000000000000000001000000000000000000110000000000000000002......18446744073709551615
最後一段是20位數,這些用log可以算得出來
實際本來的數字是這20段各自乘上不同位數(10^x)後加起來,就像是1000+200+30+4這樣
最終答案等於這20段數字各自%2018後乘上各自的位數,再%2018後再加起來再%2018

其中每一段的算法,以八位數那段為例
先算出
10000000100000011000000210000000......10002017 %2018=a
這個a數字不大,可以用很簡單、耗時短的方式算出來
然後因為在%裡面可以任意減掉2018的倍數,10002018就視同10000000
所以下一週期
10002018100020191000202010002021......10004035 %2018也=a

然後把這兩週期串起來
1000000010000001...1000201710002018...10004035 %2018
就等於
0000000000000000...0000000100000000...00000001 *a %2018 =b
這串三萬多位數的數字裡面只有兩個1其他都0,位數位置對齊上面那行
然後再*a,假設a=123那0001就替換成0123這樣
這個數字算出來再次%2018後稱為b
也就是
0000000000000000...0000000000000000...00000001 *b

再抓兩週期過來
1000000010000001...1000403510004036...10008071 %2018
就等於
0000000000000000...0000000100000000...00000001 *b %2018 =c
就這樣,每算一圈最後那個變數代表的長度就會變兩倍
到最後
1000000010000001...9999876399998764...99999999 %2018
就等於
0000000000000000...0000000z99998764...99999999 %2018
z的位置就像之前的a b c一樣展開成某個數字,可能吃掉左邊的0
(因為這次後面有別的東西所以不能把*z寫在後面,只好寫成這樣比較不正式的寫法)
z是44598個週期%出來的餘數,把44598轉換成二進制之後用前面的 一週期的a、兩週期的b、四週期的c... 各自乘上10^x後疊加出來
最後再用簡單老方法把後面那1000多個不成一週期的部份算進來
你就完整了這個八位數段

把以上這個過程對1~20位數每一段各算一次,再依照開頭說的那樣疊加起來就完成這個題目了
最長的19位數段也只需要約64圈,運算時間應該綽綽有餘
因為你沒給答案,我寫出來也不知道對不對所以就沒實際寫一趟試試
我想應該會過吧
無名18/10/19(五)02:54:26 ID:4xnmnX7YNo.12905del
>>12904
舉個簡單的例子
123456789切成12345和6789
先做12345求餘
12345 % 2018 = 237

餘數237接上6789求餘
2376789 % 2018 = 1603
此結果相當於123456789 % 2018 = 1603
依此類推做到2^64即可

不過這種方式是用程式做暴力解
快速解問數學系比較妥當
無名18/10/19(五)16:57:33 ID:96mN/.1QNo.12906del
>>12905
你這樣時間會爆掉
有2^64個數字要做,跑到宇宙死亡都還跑不出來

如果這麼簡單就能搞定的話這題不超過10行
但問題就是沒那麼簡單
無名18/10/19(五)20:12:52 ID:4xnmnX7YNo.12907del
>>12906
其實這是ID:zmy9Usb2做法的原理
他在此之外提供加速運算的方法:每個周期N(2018)的餘數相同
要再加速可以利用(m*n)%c == ((m%c)*(n%c))%c
記住10^k%2018的結果,加快串接的運算
無名18/10/21(日)04:42:05 ID:d8JXutQMNo.12908del
>>12906
感覺可以divide and conquer
每次切兩邊遞迴
應該會快很多
無名18/10/29(一)19:28:28 ID:gVtG2koMNo.12912del
原po還在嗎? 這樣應該有O(n)
double n = 2 ^ 64, k = 2018, result = 0;
for (var i = 1; i <= n; i++)
result = (result * (double)(Math.Pow(10, ((double)(i / 10) + 1))) + i) % k;
Console.WriteLine(result);
無名18/10/29(一)20:53:25 ID:CtUVx1hUNo.12913del
>>12912
這種code心智正常的人都寫得出來
問題是你一個2^64的for要跑幾年?
這題就算是O(n)也不行,要更低才可以
這題考你的就是怎麼省略,不要一個個算
無名18/10/30(二)14:48:31 ID:xryXzqSQNo.12914del
>>12913
不然還能怎麼寫? 你有什麼好方法嗎?(′・ω・‵)
無名18/10/30(二)18:01:17 ID:g4SRRKcQNo.12915del
>>12914
所以這題很難啊
不然幹嘛還要討論這麼大一串,第一篇就搞定了

然後我上面已經寫一大篇做法了
雖然很醜很難寫但至少在宇宙毀滅之前跑得完
你寫的答案就是我裡面提到的
>>這個a數字不大,可以用很簡單、耗時短的方式算出來
我沒有把這個細節寫出來,因為這是基本中的基本
連這個簡單解法都想不出來的人根本沒資格挑戰這題
無名18/10/30(二)20:36:42 ID:ZvwYUGxINo.12916del
>>12915
目前找出來的加速法沒有到很難寫吧
10^K MOD 2018很好寫就不多說了

假設N=65536
記下(9999-999) / 2018 = 4
和(9999-999) MOD 2018 = 928
4代表1000~9999要做的2018循環次數
928代表要記下100010011002..1927的結果
1000~9999一共計算2018+4+1次
以此類推做下去即可

要稍微加速2018循環計算的話
1000 MOD 2018和1001 MOD 2018其實只差1
而1000 MOD 2018在10^k次時得過答案
所以只要寫個簡單的迴圈就能處理掉了..
無名18/10/31(三)15:03:39 ID:JlE6hQDYNo.12917del
>>12912
恩恩 很棒
O(n)只要136年可以跑完
無名18/11/01(四)05:03:28 ID:TCl7dxh6No.12919del
>>12912
第一行就錯
double n = 2 ^ 64
這個叫2 xor 64


【刪除文章】[]
刪除用密碼: