QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#590050 | #249. Miller Rabin 算法 | lanhuo | Compile Error | / | / | C++17 | 1.5kb | 2024-09-25 21:14:47 | 2024-09-25 21:14:49 |
Judging History
This is the latest submission verdict.
- [2024-09-25 21:14:49]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [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){ | ^~~~~