QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#590050#249. Miller Rabin 算法lanhuoCompile Error//C++171.5kb2024-09-25 21:14:472024-09-25 21:14:49

Judging History

This is the latest submission verdict.

  • [2024-09-25 21:14:49]
  • Judged
  • [2024-09-25 21:14:47]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll prime[10] = {2,3,5,7,11,13,17,19,23,29};
ll Quick_Multiply(ll a, ll b, ll c)
{
    ll ans = 0, res = a;
    while(b)
    {
        if(b & 1)
            ans = (ans + res) % c;
        res = (res + res) % c;
        b >>= 1;
    }
    return ans;
}
ll Quick_Power(ll a, ll b, ll m)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}
bool Miller_Rabin(ll x)    //判断素数
{
    ll i, j, k;
    ll s = 0, t = x-1;
    if(x == 2) return true; //2是素数
    if(x < 2 || !(x & 1)) return false;  //如果x是偶数或者是0,1,那它不是素数
    while(!(t & 1)) //将x-1分解成(2^s)*t的样子
    {
        s++;
        t >>= 1;
    }
    for(i = 0; i < 10 && prime[i] < x; i++) //随便选一个素数进行测试
    {
        ll a = prime[i];
        ll b = Quick_Power(a, t, x);   //先算出a^t
        for(j = 1; j <= s; j++) //然后进行s次平方
        {
            k = Quick_Multiply(b,b,x);  //求b的平方
            if(k == 1 && b != 1 && b != x-1)
                return false;
            b = k;
        }
        if(b != 1) return false;    //用费马小定理判断
    }
    return true;    //如果进行多次测试都是对的,那么x就很有可能是素数
}

int main()
{
    ll x;
    whlie(cin>>x){
    if(Miller_Rabin(x)) printf("Y");
    else printf("N");
}
    return 0;
}

详细

answer.code: In function ‘int main()’:
answer.code:61:5: error: ‘whlie’ was not declared in this scope
   61 |     whlie(cin>>x){
      |     ^~~~~