51nod1186(Miller-Rabin)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1186

题意：中文题目诶～

思路：miller_rabin模板 (详情可参见: http://blog.csdn.net/s031302306/article/details/51606018)

注意这里的 n 为 1e30，需要用字符串处理

代码：

 #include <string.h>

 #include <cstdlib>

 #define MAXL 4

 #define M10 1000000000

 #define Z10 9

 const int zero[MAXL - ] = {};

 struct bnum{

     int data[MAXL]; //  断成每截9个长度

     //  读取字符串并转存

     void read(){

         memset(data, , sizeof(data));

         char buf[];

         scanf("%s", buf);

         int len = (int)strlen(buf);

         int i = , k;

         while (len >= Z10){

             for (k = len - Z10; k < len; ++k){

                 data[i] = data[i] *  + buf[k] - '';

             }

             ++i;

             len -= Z10;

         }

         if (len > ){

             for (k = ; k < len; ++k){

                 data[i] = data[i] *  + buf[k] - '';

             }

         }

     }

     bool operator == (const bnum &x){

         return memcmp(data, x.data, sizeof(data)) == ;

     }

     bnum & operator = (const int x){

         memset(data, , sizeof(data));

         data[] = x;

         return *this;

     }

     bnum operator + (const bnum &x){

         int i, carry = ;

         bnum ans;

         for (i = ; i < MAXL; ++i){

             ans.data[i] = data[i] + x.data[i] + carry;

             carry = ans.data[i] / M10;

             ans.data[i] %= M10;

         }

         return  ans;

     }

     bnum operator - (const bnum &x){

         int i, carry = ;

         bnum ans;

         for (i = ; i < MAXL; ++i){

             ans.data[i] = data[i] - x.data[i] - carry;

             if (ans.data[i] < ){

                 ans.data[i] += M10;

                 carry = ;

             }else{

                 carry = ;

             }

         }

         return ans;

     }

     //  assume *this < x * 2

     bnum operator % (const bnum &x){

         int i;

         for (i = MAXL - ; i >= ; --i){

             if (data[i] < x.data[i]){

                 return *this;

             }

             else if (data[i] > x.data[i]){

                 break;

             }

         }

         return ((*this) - x);

     }

     bnum & div2(){

         int  i, carry = , tmp;

         for (i = MAXL - ; i >= ; --i){

             tmp = data[i] & ;

             data[i] = (data[i] + carry) >> ;

             carry = tmp * M10;

         }

         return *this;

     }

     bool is_odd(){

         return (data[] & ) == ;

     }

     bool is_zero(){

         for (int i = ; i < MAXL; ++i){

             if (data[i]){

                 return false;

             }

         }

         return true;

     }

 };

 void mulmod(bnum &a0, bnum &b0, bnum &p, bnum &ans){//计算a0*b0%p

     ans = ;

     bnum tmp = a0, b = b0;

     while (!b.is_zero()){

         if (b.is_odd()){

             ans = (ans + tmp) % p;

         }

         tmp = (tmp + tmp) % p;

         b.div2();

     }

 }

 void powmod(bnum &a0, bnum &b0, bnum &p, bnum &ans){//计算a0^b0%p

     bnum tmp = a0, b = b0;

     ans = ;

     while (!b.is_zero()){

         if (b.is_odd()){

             mulmod(ans, tmp, p, ans);

         }

         mulmod(tmp, tmp, p, tmp);

         b.div2();

     }

 }

 bool MillerRabinTest(bnum &p, int iter){

     int i, small = , j, d = ;

     for (i = ; i < MAXL; ++i){

         if (p.data[i]){

             break;

         }

     }

     if (i == MAXL){

         // small integer test

         if (p.data[] < ){

             return  false;

         }

         if (p.data[] == ){

             return  true;

         }

         small = ;

     }

     if (!p.is_odd()){

         return false;   //  even number

     }

     bnum a, s, m, one, pd1;

     one = ;

     s = pd1 = p - one;

     while (!s.is_odd()){

         s.div2();

         ++d;

     }

     for (i = ; i < iter; ++i){

         a = rand();

         if (small){

             a.data[] = a.data[] % (p.data[] - ) + ;

         }else{

             a.data[] = a.data[] / M10;

             a.data[] %= M10;

         }

         if (a == one){

             continue;

         }

         powmod(a, s, p, m);

         for (j = ; j < d && !(m == one) && !(m == pd1); ++j){

             mulmod(m, m, p, m);

         }

         if (!(m == pd1) && j > ){

             return false;

         }

     }

     return true;

 }

 int main(void){

     bnum x;

     x.read();

     puts(MillerRabinTest(x, ) ? "Yes" : "No");

     return ;

 }

对于long long范围：

 #include <stdio.h>

 #include <iostream>

 #include <cstdlib>

 #define ll long long

 using namespace std;

 //利用二进制计算a*b%mod

 ll multi_mod(ll a, ll b, ll mod){

     ll ans = 0LL;

     a %= mod;

     while(b){

         if (b & 1LL) ans = (ans+a)%mod;

         b >>= 1LL;

         a = (a+a)%mod;

     }

     return ans;

 }

 //计算a^b%mod

 ll power_mod(ll a, ll b, ll mod){

     ll ans = 1LL;

     a %= mod;

     while(b){

         if(b & 1LL) ans = multi_mod(ans, a, mod);

         b >>= 1LL;

         a = multi_mod(a, a, mod);

     }

     return ans;

 }

 //Miller-Rabin测试,测试n是否为素数

 bool miller_rabin(ll n, int repeat){

     if (2LL == n || 3LL == n) return true;

     if (n%== || n%== || n%==) return false;

     //将n分解为2^s*d

     ll d = n - 1LL;

     int s = ;

     while(!(d & 1LL)){

         s++;

         d >>= 1LL;

     }

     // srand((unsigned)time(0));

     for(int i=; i<repeat; ++i){//重复repeat次

         ll a = rand() % (n - ) + ;//取一个随机数,[2,n-1)

         ll x = power_mod(a, d, n);

         ll y = 0LL;

         for(int j=; j<s; ++j){

             y = multi_mod(x, x, n);

             if (1LL == y && 1LL != x && n-1LL != x) return false;

             x = y;

         }

         if (1LL != y) return false;

     }

     return true;

 }

 int main(void){

     ll n;

     cin >> n;

     if(miller_rabin(n, )) cout << "Yes" << endl;

     else cout << "No" << endl;

     return ;

 }

巴特西

51nod1186(Miller-Rabin)

最新文章

热门文章