Advertisement
PikMike

Untitled

Jan 29th, 2017
545
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define mp make_pair
  5. #define sz(x) (int)(x).size()
  6. #define li long long
  7. #define ld long double
  8. #define x first
  9. #define y second
  10. #define pt pair<int, int>
  11. #define pll pair<ll, ll>
  12. #define forn(i, t) for(int i = 0; i < (t); i++)
  13. #define fore(i, f, t) for(int i = (f); i < (t); i++)
  14. #define forr(i, f, t) for(int i = (f) - 1; i >= (t); i--)
  15. #define all(x) (x).begin(), (x).end()
  16. #define ins insert
  17.  
  18. using namespace std;
  19.  
  20.  
  21. const int INF = 1e9;
  22. const int MOD = 1000000007;
  23. const li INF64 = 1e18;
  24. const ld EPS = 1e-7;
  25.  
  26. mt19937 myrand(time(NULL));
  27.  
  28. const int N = 200;
  29.  
  30. int d, k;
  31.  
  32.  
  33. bool read(){
  34.     if(scanf("%d%d", &k, &d) != 2)
  35.         return 0;
  36.     return 1;
  37. }
  38.  
  39.  
  40. void solve(){
  41.     pt dp[N];
  42.  
  43.     dp[1] = mp(1, 0);
  44.     fore(i, 2, d + 1){
  45.         if (k % i == 0){
  46.             dp[i] = mp(2, 1);
  47.             continue;
  48.         }
  49.         if ((k - 1) % i == 0){
  50.             dp[i] = mp(3, 0);
  51.             continue;
  52.         }
  53.         if ((k + 1) % i == 0){
  54.             dp[i] = mp(11, 0);
  55.             continue;
  56.         }
  57.         dp[i] = mp(7, INF);
  58.         fore(j, 2, i)
  59.             if (i % j == 0){
  60.                 if (dp[j].x == 2 && dp[i / j].x == 2)
  61.                     dp[i] = mp(2, min(dp[i].y, dp[j].y + dp[i / j].y));
  62.                 else if (dp[j].x == 2 && (dp[i / j].x == 3 || dp[i / j].x == 11))
  63.                     dp[i] = mp(6, 0);
  64.                 else if (dp[i / j].x == 2 && (dp[j].x == 3 || dp[j].x == 11))
  65.                     dp[i] = mp(6, 0);
  66.                 else if (dp[j].x == 3 && dp[i / j].x == 11 && __gcd(j, i / j) == 1)
  67.                     dp[i] = mp(6, 0);
  68.                 else if (dp[j].x == 11 && dp[i / j].x == 3 && __gcd(j, i / j) == 1)
  69.                     dp[i] = mp(6, 0);
  70.                 else if (dp[j].x == 6 && dp[i / j].x != 7)
  71.                     dp[i] = mp(6, 0);
  72.                 else if (dp[i / j].x == 6 && dp[j].x != 7)
  73.                     dp[i] = mp(6, 0);
  74.             }
  75.     }
  76.    
  77.     /*fore(i, 1, d + 1)
  78.         printf("[%d %d] ", dp[i].x, dp[i].y);
  79.     printf("\n");*/
  80.  
  81.     bool fl2 = (dp[d].x == 2 ||dp[d].x == 6);
  82.     bool fl3 = (dp[d].x == 3 || dp[d].x == 6);
  83.     bool fl11 = (dp[d].x == 11 || dp[d].x == 6);
  84.    
  85.     if (fl2 && (fl3 || fl11)){
  86.         printf("6-type\n");
  87.         return;
  88.     }
  89.     if (fl3){
  90.         printf("3-type\n");
  91.         return;
  92.     }
  93.     if (fl11){
  94.         printf("11-type\n");
  95.         return;
  96.     }
  97.     if (fl2){
  98.         printf("2-type\n%d\n", dp[d].y);
  99.         return;
  100.     }
  101.     //printf("%d %d: ", k, d);
  102.     printf("7-type\n");
  103. }
  104.  
  105.  
  106. int main(){
  107.     #ifdef _DEBUG
  108.         freopen("input.txt", "r", stdin);
  109.     #endif
  110.     while(read())
  111.         solve();
  112.     return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement