数据没问题,估计是因为这个数是个超大质数,然后Boom(
by Karl_Aurora @ 2021-05-04 16:17:05
4969*1459987114088231,没问题,是 NO
by Fatalis_Lights @ 2021-05-04 16:18:09
@[SolitaryLyrique](/user/91204) az
by Karl_Aurora @ 2021-05-04 16:18:48
~~好耶,我的没被卡~~
by zltqwq @ 2021-05-04 16:18:56
可能我开了 __int128 所以没事
by Fatalis_Lights @ 2021-05-04 16:19:04
@[zltzlt](/user/275273) 可以放一下您的代码吗
by Fool_Fish @ 2021-05-04 16:23:21
题解在ide上测这个数据TLE了。。
by Fatalis_Lights @ 2021-05-04 16:23:32
尝试提供代码
```cpp
#include<bits/stdc++.h>
#define times 10
#define N 6081
#define ll __int128
#define int __int128
using namespace std;
ll T,n;
inline __int128 read(){
__int128 x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void print(__int128 x){
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
inline ll ksc(ll a, ll b, ll m){
ll res=0; a%=m;
while(b){
if(b&1){ res=(res+a)%m; b--; }
b>>=1; a=(a+a)%m;
}
return res;
}
inline ll ksm(ll a, ll b, ll m){
ll res=1; a%=m;
while(b){
if(b&1){ res=ksc(res,a,m); b--; }
b>>=1; a=ksc(a,a,m);
}
return res;
}
inline bool Miller_Rabin(ll n){
if(n==2) return true;
if(n<2 || !(n&1)) return false;
ll m=n-1;
int k=0;
while((m&1)==0) k++, m>>=1;
for(int i=0;i<times;i++){
ll a=rand()%(n-1)+1;
ll x=ksm(a,m,n);
ll y=0;
for(int j=0;j<k;j++){
y=ksc(x,x,n);
if(y==1 && x!=1 && x!=n-1) return false;
x=y;
}
if(y!=1) return false;
}
return true;
}
signed main(){
T=read();
while(T--){
n=read();
if(Miller_Rabin(n)) puts("YES");
else puts("NO");
}
return 0;
}
```
by Fatalis_Lights @ 2021-05-04 16:24:23
@[Fool_Fish](/user/247555) https://www.luogu.com.cn/paste/whp1ru4x
~~难道是因为我开了 `__int128`?~~
by zltqwq @ 2021-05-04 16:24:47
我貌似发现问题了,题解的代码在快速幂中有一步res变成了负的
by Fool_Fish @ 2021-05-04 16:27:03