fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <boost/multiprecision/cpp_int.hpp>
  4. using boost::multiprecision::cpp_int;
  5. #define ll long long
  6.  
  7. using u64  = uint64_t;
  8. using u128 = unsigned __int128;
  9.  
  10. u128 limit = u128(1) << 64;
  11.  
  12. static constexpr u64 bases[] = 
  13. {2ULL, 325ULL, 9375ULL, 28178ULL,450775ULL,9780504ULL, 1795265022ULL};
  14.  
  15. static constexpr u64 small_primes[] = 
  16. {2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL};
  17.  
  18. u128 modpow(u128 base, u128 expo, u128& mod){
  19.   u128 res = 1;
  20.   base %= mod;
  21.   while(expo){
  22.     if(expo&1) res = (u128) (cpp_int(res)*base %mod);
  23.     base = (u128) (cpp_int(base)*base %mod);
  24.     expo >>= 1;
  25.     }
  26. return res;
  27. }
  28.  
  29. bool isComposite(u128 a, u128 d, int s, u128& n){
  30.  
  31.   u128 x = modpow(a, d, n);
  32.   if(x==1 || x==n-1) return false;
  33.  
  34.   for(int r=1; r<s; r++){
  35.     x = (u128) (cpp_int(x)*x %n);
  36.     if(x==n-1) return false;
  37.     }
  38. return true;
  39. }
  40.  
  41. bool isPrime(u128 n){
  42.  
  43.   if(n<2) return false;
  44.  
  45.   for(u64 p : small_primes){
  46.     if(n==p) return true;
  47.     if(n%p==0) return false;
  48.     }
  49.  
  50.     u128 d = n-1;
  51.     int s = __builtin_ctzll(d);
  52.     d >>= s;
  53.  
  54.   for(u64 a : bases){
  55.     if(a%n==0) continue;
  56.     if(isComposite(a, d, s, n)) return false;
  57.     }
  58.  
  59.   if(n>limit){
  60.  
  61.   	random_device rd;
  62.     mt19937 gen(rd());
  63.     uniform_int_distribution<u64> dist(2, LLONG_MAX);
  64.  
  65.     for(int i=0; i<5; i++){
  66.     u64 z = dist(gen);
  67.     if(isComposite(z, d, s, n)) return false;
  68.     }
  69.  
  70.   }  
  71. return true;
  72. }
  73.  
  74. unordered_map<string,ll>mp;
  75.  
  76. ll fn(string s){
  77.  
  78. if(s.size()==0) return 1;
  79.  
  80. if(mp[s]!=0){
  81.   if(mp[s]==-1) return 0;
  82.   return mp[s];
  83. }
  84.  
  85. ll count = 0;	
  86. u128 num = 0;
  87.  
  88. for(int i=0; i<s.size(); i++){
  89.  
  90. num = num*10 + s[i]-'0';	
  91. if(isPrime(num)) count += fn(s.substr(i+1));	
  92.  
  93. }	
  94.  
  95. if(count==0) { mp[s]=-1; return 0; }	
  96. return mp[s]=count;	
  97. }
  98.  
  99.  
  100.  
  101.  
  102. int main() {
  103.  
  104. int t; cin >> t;
  105.  
  106. for(int i=0; i<t; i++){
  107.   string s; cin >> s;
  108.   cout<<fn(s)<<endl;
  109.   mp.clear();
  110. }
  111.  
  112. return 0;
  113. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
8
2
37
111
3737
133
1000000009
113731191937237
1111111111111111111111
stdout
copy 
1
2
0
6
1
1
197
1
https://ideone.com/CBUtOO
language:
C++ (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!