CodeForcesGym 100753K Upside down primes

Upside down primes

Time Limit: 2000ms

Memory Limit: 262144KB

This problem will be judged on CodeForcesGym. Original ID: 100753K
64-bit integer IO format: %I64d Java class name: (Any)

解题：大数素性测试

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL mul(LL a,LL b,LL mod) {
 5     if(!a) return 0;
 6     return ((a&1)*b%mod + (mul(a>>1,b,mod)<<1)%mod)%mod;
 7 }
 8 LL quickPow(LL a,LL d,LL n){
 9     LL ret = 1;
10     while(d){
11         if(d&1) ret = mul(ret,a,n);
12         d >>= 1;
13         a = mul(a,a,n);
14     }
15     return ret;
16 }
17 bool check(LL a,LL d,LL n){
18     if(n == a) return true;
19     while(~d&1) d >>= 1;
20     LL t = quickPow(a,d,n);
21     while(d < n-1 && t != 1 && t != n-1){
22         t = mul(t,t,n);
23         d <<= 1;
24     }
25     return (d&1)||t == n-1;
26 }
27 bool isP(LL n){
28     if(n == 2) return true;
29     if(n < 2 || 0 == (n&1)) return false;
30     static int p[10] = {2,3,5,7,11,61,24251};
31     for(int i = 0; i < 7; ++i)
32         if(!check(p[i],n-1,n)) return false;
33     return true;
34 }
35 
36 bool trans(LL x){
37     char str[100];
38     sprintf(str,"%I64d",x);
39     for(int i = 0; str[i]; ++i)
40         if(str[i] == '3' || str[i] == '4' || str[i] == '7') return false;
41     reverse(str,str + strlen(str));
42     for(int i = 0; str[i]; ++i)
43         if(str[i] == '6') str[i] = '9';
44         else if(str[i] == '9') str[i] = '6';
45     sscanf(str,"%I64d",&x);
46     return isP(x);
47 }
48 int main(){
49     LL x;
50     while(~scanf("%I64d",&x)){
51         if(isP(x) && trans(x)) puts("yes");
52         else puts("no");
53     }
54     return  0;
55 }

View Code