\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年1月31日 星期日

[ Miller-Rabin Strong Probable-prime Base ] 質數測試算法保證long long範圍內正確

這本來是隨機演算法,但是已經有一些人,找出一些特定底數,保證判定結果在某些範圍內正確。

如果是unsigned long long範圍內東西記得要用long long乘long long mod long long 的模板
這裡的範例已經加在code裡了,如果不需要可以把它拿掉(zerojudge a007不拿掉會變慢)

code:

1 則留言:

  1. 那個 for(int j=0;j<t;++j) 是不是多跑了一次?
    這樣是把 a^(n-1) mod n = n-1 的情況判成通過測試,就失去了一個 witness。
    不過隨意生些數值來測,完全沒有碰到這種情況就是了。
    或許其實可以證明不存在這種情況?

    回覆刪除