51nod 1106 质数检测(miller rabin 素数测试.)
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
收藏
关注
给出N个正整数，检测每个数是否为质数。如果是，输出"Yes"，否则输出"No"。
Input
第1行：一个数N，表示正整数的数量。(1 <= N <= 1000)
第2 - N + 1行：每行1个数(2 <= S[i] <= 10^9)
Output
输出共N行，每行为 Yes 或 No。
Input示例
5
2
3
4
5
6
Output示例
Yes
Yes
No
Yes
No<br></br><br></br>miller rabin 素数测试...
<span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008000;">************************************************************************
</span><span style="color: #008080;"> 2</span> <span style="color: #008000;"> > File Name: code/51nod/1106.cpp
</span><span style="color: #008080;"> 3</span> <span style="color: #008000;"> > Author: 111qqz
</span><span style="color: #008080;"> 4</span> <span style="color: #008000;"> > Email: rkz2013@126.com
</span><span style="color: #008080;"> 5</span> <span style="color: #008000;"> > Created Time: 2015年10月19日 星期一 18时51分06秒
</span><span style="color: #008080;"> 6</span> <span style="color: #008000;"> ***********************************************************************</span><span style="color: #008000;">*/</span>
<span style="color: #008080;"> 7</span>
<span style="color: #008080;"> 8</span> #include<iostream>
<span style="color: #008080;"> 9</span> #include<iomanip>
<span style="color: #008080;">10</span> #include<cstdio>
<span style="color: #008080;">11</span> #include<algorithm>
<span style="color: #008080;">12</span> #include<cmath>
<span style="color: #008080;">13</span> #include<cstring>
<span style="color: #008080;">14</span> #include<<span style="color: #0000ff;">string</span>>
<span style="color: #008080;">15</span> #include<map>
<span style="color: #008080;">16</span> #include<<span style="color: #0000ff;">set</span>>
<span style="color: #008080;">17</span> #include<queue>
<span style="color: #008080;">18</span> #include<vector>
<span style="color: #008080;">19</span> #include<stack>
<span style="color: #008080;">20</span> #include<cctype>
<span style="color: #008080;">21</span>
<span style="color: #008080;">22</span> <span style="color: #0000ff;">#define</span> yn hez111qqz
<span style="color: #008080;">23</span> <span style="color: #0000ff;">#define</span> j1 cute111qqz
<span style="color: #008080;">24</span> <span style="color: #0000ff;">#define</span> ms(a,x) memset(a,x,sizeof(a))
<span style="color: #008080;">25</span> <span style="color: #0000ff;">using</span> <span style="color: #0000ff;">namespace</span><span style="color: #000000;"> std;
</span><span style="color: #008080;">26</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dx4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span>,<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span><span style="color: #000000;">};
</span><span style="color: #008080;">27</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dy4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span>,<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span><span style="color: #000000;">};
</span><span style="color: #008080;">28</span> typedef <span style="color: #0000ff;">long</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> LL;
</span><span style="color: #008080;">29</span> typedef <span style="color: #0000ff;">double</span><span style="color: #000000;"> DB;
</span><span style="color: #008080;">30</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> inf = <span style="color: #800080;">0x3f3f3f3f</span><span style="color: #000000;">;
</span><span style="color: #008080;">31</span>
<span style="color: #008080;">32</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> witness(LL a,LL n)
</span><span style="color: #008080;">33</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">34</span> <span style="color: #000000;"> LL t,d,x;
</span><span style="color: #008080;">35</span> d=<span style="color: #800080;">1</span><span style="color: #000000;">;
</span><span style="color: #008080;">36</span> <span style="color: #0000ff;">int</span> i=ceil(log(n-<span style="color: #800080;">1.0</span>)/log(<span style="color: #800080;">2.0</span>)) - <span style="color: #800080;">1</span><span style="color: #000000;">;
</span><span style="color: #008080;">37</span> <span style="color: #0000ff;">for</span>(;i>=<span style="color: #800080;">0</span>;i--<span style="color: #000000;">)
</span><span style="color: #008080;">38</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">39</span> x=d; d=(d*d)%<span style="color: #000000;">n;
</span><span style="color: #008080;">40</span> <span style="color: #0000ff;">if</span>(d==<span style="color: #800080;">1</span> && x!=<span style="color: #800080;">1</span> && x!=n-<span style="color: #800080;">1</span>) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;">41</span> <span style="color: #0000ff;">if</span>( ((n-<span style="color: #800080;">1</span>) & (<span style="color: #800080;">1</span><<i))> <span style="color: #800080;">0</span><span style="color: #000000;">)
</span><span style="color: #008080;">42</span> d=(d*a)%<span style="color: #000000;">n;
</span><span style="color: #008080;">43</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">44</span> <span style="color: #0000ff;">return</span> d==<span style="color: #800080;">1</span>? <span style="color: #0000ff;">false</span> : <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;">45</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">46</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> miller_rabin(LL n)
</span><span style="color: #008080;">47</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">48</span> <span style="color: #0000ff;">if</span>(n==<span style="color: #800080;">2</span>) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;">49</span> <span style="color: #0000ff;">if</span>(n==<span style="color: #800080;">1</span> || ((n&<span style="color: #800080;">1</span>)==<span style="color: #800080;">0</span>)) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;">50</span> <span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i=<span style="color: #800080;">0</span>;i<<span style="color: #800080;">50</span>;i++<span style="color: #000000;">){
</span><span style="color: #008080;">51</span> LL a=rand()*(n-<span style="color: #800080;">2</span>)/RAND_MAX +<span style="color: #800080;">1</span><span style="color: #000000;">;
</span><span style="color: #008080;">52</span> <span style="color: #0000ff;">if</span>(witness(a, n)) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
</span><span style="color: #008080;">53</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">54</span> <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
</span><span style="color: #008080;">55</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">56</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> main()
</span><span style="color: #008080;">57</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">58</span>
<span style="color: #008080;">59</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> n,cnt;
</span><span style="color: #008080;">60</span> <span style="color: #000000;"> LL a;
</span><span style="color: #008080;">61</span> <span style="color: #0000ff;">while</span>(scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d</span><span style="color: #800000;">"</span>,&n;)!=<span style="color: #000000;">EOF)
</span><span style="color: #008080;">62</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">63</span> cnt=<span style="color: #800080;">0</span><span style="color: #000000;">;
</span><span style="color: #008080;">64</span> <span style="color: #0000ff;">while</span>(n--<span style="color: #000000;">)
</span><span style="color: #008080;">65</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">66</span> scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%lld</span><span style="color: #800000;">"</span>,&<span style="color: #000000;">a);
</span><span style="color: #008080;">67</span> <span style="color: #0000ff;">if</span><span style="color: #000000;">(miller_rabin(a))
</span><span style="color: #008080;">68</span> puts(<span style="color: #800000;">"</span><span style="color: #800000;">Yes</span><span style="color: #800000;">"</span><span style="color: #000000;">);
</span><span style="color: #008080;">69</span> <span style="color: #0000ff;">else</span>
<span style="color: #008080;">70</span> puts(<span style="color: #800000;">"</span><span style="color: #800000;">No</span><span style="color: #800000;">"</span><span style="color: #000000;">);
</span><span style="color: #008080;">71</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">72</span> <span style="color: #008000;">//</span><span style="color: #008000;"> printf("%dn",cnt);</span>
<span style="color: #008080;">73</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">74</span> <span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;
</span><span style="color: #008080;">75</span> }
View Code