fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  3. #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
  4. #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
  5. #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
  6. #define ALL(v) (v).begin(), (v).end()
  7. #define IS_INF(x)   (std::isinf(x))
  8. #define IS_NAN(x)   (std::isnan(x))
  9. #define fi   first
  10. #define se   second
  11. #define MASK(i) (1LL << (i))
  12. #define BIT(x, i) (((x) >> (i)) & 1)
  13. #define div   ___div
  14. #define next   ___next
  15. #define prev   ___prev
  16. #define left   ___left
  17. #define right   ___right
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<class X, class Y>
  21.     bool minimize(X &x, const Y &y) {
  22.         X eps = 1e-9;
  23.         if (x > y + eps) {
  24.             x = y;
  25.             return true;
  26.         } else return false;
  27.     }
  28. template<class X, class Y>
  29.     bool maximize(X &x, const Y &y) {
  30.         X eps = 1e-9;
  31.         if (x + eps < y) {
  32.             x = y;
  33.             return true;
  34.         } else return false;
  35.     }
  36. template<class T>
  37.     T Abs(const T &x) {
  38.         return (x < 0 ? -x : x);
  39.     }
  40.  
  41. /* Author: Van Hanh Pham */
  42.  
  43. /** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/
  44.  
  45. #define HEXA_MASK(i) MASK((i) << 2)
  46. #define HEXA_DIGIT(x, i) (((x) >> ((i) << 2)) & 15)
  47. #define CLEAR_HEXA_DIGIT(x, i) ((x) & ~(15 << ((i) << 2)))
  48. #define SET_HEXA_DIGIT(x, i, d) (CLEAR_HEXA_DIGIT(x, i) ^ ((d) << ((i) << 2)))
  49.  
  50. #define LENGTH   5
  51. #define BLANK   10
  52. #define VALUE   100100
  53. vector<int> primes[LENGTH + 1][HEXA_MASK(LENGTH) + 1];
  54. bool notPrime[VALUE];
  55.  
  56. // least significant digit in x becomes most significant digit in the hexa code
  57. int toHexa(int x, int numDigit) {
  58.     int res = 0;
  59.     REP(love, numDigit) {
  60.         res = (res << 4) ^ (x % 10);
  61.         x /= 10;
  62.     }
  63.     return x > 0 ? -1 : res;
  64. }
  65.  
  66. void prepare(void) {
  67.     REP(i, 2) notPrime[i] = true;
  68.     FOR(i, 2, VALUE - 1) if (!notPrime[i]) for (int j = 2 * i; j < VALUE; j += i) notPrime[j] = true;
  69.  
  70.     FOR(i, 2, VALUE - 1) if (!notPrime[i]) FOR(length, 1, LENGTH) {
  71.         int code = toHexa(i, length);
  72.         if (code < 0) continue;
  73.  
  74.         REP(mask, MASK(length)) {
  75.             int newCode = code;
  76.             REP(i, length) if (BIT(mask, i)) newCode = SET_HEXA_DIGIT(newCode, i, BLANK);
  77.             primes[length][newCode].push_back(code);
  78.         }
  79.     }
  80. }
  81.  
  82. int res;
  83. void backtrack(vector<int> &state, int filled) {
  84.     int numRow = state.size();
  85.     if (__builtin_popcount(filled) == numRow) {
  86.         res++;
  87.         return;
  88.     }
  89.  
  90.     int row = -1, numCandidate = VALUE;
  91.     if (!BIT(filled, numRow - 1)) {
  92.         row = numRow - 1;
  93.         numCandidate = primes[numRow][state[row]].size();
  94.     } else {
  95.         REP(i, numRow) if (!BIT(filled, i)) {
  96.             int tmpCandidate = primes[numRow][state[i]].size();
  97.             if (minimize(numCandidate, tmpCandidate)) row = i;
  98.         }
  99.     }
  100.  
  101.     if (numCandidate == 0) return;
  102.     if (__builtin_popcount(filled) == numRow - 1) {
  103.         res += numCandidate;
  104.         return;
  105.     }
  106.  
  107.     int oldState = state[row];
  108.  
  109.     vector<int> &candidates = primes[numRow][oldState];
  110.     FORE(it, candidates) {
  111.         REP(j, numRow) {
  112.             // state[row][j] = state[j][row] = HEXA_DIGIT(*it, j)
  113.             state[row] = SET_HEXA_DIGIT(state[row], j, HEXA_DIGIT(*it, j));
  114.             state[j] = SET_HEXA_DIGIT(state[j], row, HEXA_DIGIT(*it, j));
  115.         }
  116.         backtrack(state, filled | MASK(row));
  117.     }
  118.  
  119.     state[row] = oldState;
  120.     REP(i, numRow) state[i] = SET_HEXA_DIGIT(state[i], row, HEXA_DIGIT(oldState, i));
  121. }
  122.  
  123. int numDigit(int x) {
  124.     return x < 10 ? 1 : numDigit(x / 10) + 1;
  125. }
  126.  
  127. int solve(int x) {
  128.     int numRow = numDigit(x);
  129.     int code = toHexa(x, numRow);
  130.     vector<int> state(numRow, 0);
  131.  
  132.     REP(i, numRow) REP(j, numRow) // state[i][j] = BLANK
  133.         state[i] = SET_HEXA_DIGIT(state[i], j, BLANK);
  134.  
  135.     REP(i, numRow) {
  136.         // state[0][i] = state[i][0] = HEXA_DIGIT(code, i)
  137.         state[0] = SET_HEXA_DIGIT(state[0], i, HEXA_DIGIT(code, i));
  138.         state[i] = SET_HEXA_DIGIT(state[i], 0, HEXA_DIGIT(code, i));
  139.     }
  140.  
  141.     res = 0;
  142.     backtrack(state, MASK(0));
  143.     return res;
  144. }
  145.  
  146. int main(void) {
  147. #ifdef ONLINE_JUDGE
  148.     freopen("primetable.inp", "r", stdin);
  149.     freopen("primetable.out", "w", stdout);
  150. #endif // ONLINE_JUDGE
  151.  
  152.     prepare();
  153.     int t; scanf("%d", &t);
  154.     REP(love, t) {
  155.         int x; scanf("%d", &x);
  156.         printf("%d ", solve(x));
  157.     }
  158.     printf("\n");
  159.     return 0;
  160. }
  161.  
  162. /*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/
Success #stdin #stdout 0.05s 153760KB
comments (?)
stdin
copy 
1
239
stdout
copy 
Standard output is empty
https://ideone.com/ojEuq2
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 day 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!