Guest User

Untitled

a guest
Oct 20th, 2016
150
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*input
  2.  
  3. */
  4. #include <bits/stdc++.h>
  5. #include<stdio.h>
  6. using namespace std;
  7. #define F(i,a,b) for(int i = a; i <= b; i++)
  8. #define RF(i,a,b) for(int i = a; i >= b; i--)
  9. #define pii pair<int,int>
  10. #define PI 3.14159265358979323846264338327950288
  11. #define ll long long
  12. #define ff first
  13. #define ss second
  14. #define pb(x) push_back(x)
  15. #define mp(x,y) make_pair(x,y)
  16. #define debug(x) cout << #x << " = " << x << endl
  17. #define INF 1000000009
  18. #define S(x) scanf("%d",&x)
  19. #define S2(x,y) scanf("%d%d",&x,&y)
  20. #define P(x) printf("%d\n",x)
  21. #define all(v) v.begin(),v.end()
  22. #define MX 200005
  23. ll a,k,n;
  24. ll primes[5] = {2,3,5,7,11};
  25. vector < ll > arr[5];
  26. int main()
  27. {
  28.     std::ios::sync_with_stdio(false);
  29.     ll temp = 1;
  30.     F(i,0,63)
  31.     {
  32.         arr[0].pb(temp);
  33.         temp = temp*2;
  34.         if(temp <= 0)
  35.             break;
  36.     }
  37.     temp = 1;
  38.     F(i,0,39)
  39.     {
  40.         arr[1].pb(temp);
  41.         temp = temp*3;
  42.         if(temp <= 0)
  43.             break;
  44.     }
  45.     temp = 1;
  46.     F(i,0,27)
  47.     {
  48.         arr[2].pb(temp);
  49.         temp = temp*5;
  50.         if(temp <= 0)
  51.             break;
  52.     }
  53.     temp = 1;
  54.     F(i,0,22)
  55.     {
  56.         arr[3].pb(temp);
  57.         temp = temp*7;
  58.         if(temp <= 0)
  59.             break;
  60.     }
  61.     temp = 1;
  62.     F(i,0,18)
  63.     {
  64.         arr[4].pb(temp);
  65.         temp = temp*11;
  66.         if(temp <= 0)
  67.             break;
  68.     }
  69.     F(i,0,63)
  70.     {
  71.         F(j,1,39)
  72.         {
  73.             if(i==0)
  74.                 continue;
  75.             ll temp = (arr[0][i]) * (arr[1][j]);
  76.             if(temp <= 0 || temp < arr[0][i] || temp<arr[1][j])
  77.                 break;
  78.             arr[1].pb(temp);
  79.         }
  80.     }
  81.     F(i,0,63)
  82.     {
  83.         F(j,0,39)
  84.         {
  85.             F(k,1,27)
  86.             {
  87.                 if(i==0 && j==0)
  88.                     continue;
  89.                 ll temp = (arr[0][i]) * (arr[1][j]) * (arr[2][k]);
  90.                 if(temp <= 0 || temp < arr[0][i] || temp<arr[1][j] || temp<arr[2][k])
  91.                     break;
  92.                 arr[2].pb(temp);
  93.             }
  94.         }
  95.     }
  96.     F(i,0,63)
  97.     {
  98.         F(j,0,39)
  99.         {
  100.             F(k,0,27)
  101.             {
  102.                 F(l,1,22)
  103.                 {
  104.                     if(i==0 && j==0 && k==0)
  105.                         continue;
  106.                     temp = (arr[0][i]) * (arr[1][j]) * (arr[2][k]) * (arr[3][l]);
  107.                     if(temp <= 0 || temp < arr[0][i] || temp<arr[1][j] || temp<arr[2][k] || temp < arr[3][l])
  108.                         break;
  109.                     arr[3].pb(temp);
  110.                 }
  111.             }
  112.         }
  113.     }
  114.     F(i,0,63)
  115.     {
  116.         F(j,0,39)
  117.         {
  118.             F(k,0,27)
  119.             {
  120.                 F(l,0,22)
  121.                 {
  122.                     F(m,1,18)
  123.                     {
  124.                         if(i==0 && j==0 && k==0 && l==0)
  125.                             continue;
  126.                         ll temp = (arr[0][i]) * (arr[1][j]) * (arr[2][k]) * (arr[3][l]) * (arr[4][m]);
  127.                         if(temp <= 0 || temp < arr[0][i] || temp<arr[1][j] || temp<arr[2][k] || temp < arr[3][l] || temp < arr[4][m])
  128.                             break;
  129.                         arr[4].pb(temp);
  130.                     }
  131.                 }
  132.             }
  133.         }
  134.     }
  135.     F(i,0,4)
  136.         sort(arr[i].begin(),arr[i].end());
  137.     /*F(i,0,62)
  138.     {
  139.         cout<<arr[0][i]<<endl;
  140.     }*/
  141.     ll t;
  142.     cin>>t;
  143.     while(t--)
  144.     {
  145.         ll ans;
  146.         cin>>a>>k>>n;
  147.         if(n==0)
  148.         {
  149.             cout<<a<<endl;
  150.             continue;
  151.         }
  152.         else if(n==1)
  153.         {
  154.             vector <ll>::iterator it;
  155.             ll id;
  156.             F(i,0,4)
  157.             {
  158.                 if(primes[i] == k)
  159.                     id = i;
  160.             }
  161.             it = lower_bound(arr[id].begin(),arr[id].end(),a);
  162.             if(*it == a)
  163.             {
  164.                 it = it + n-1;
  165.                 ans = *it;
  166.             }
  167.             else
  168.             {
  169.                 //debug(*it);
  170.                 it = it + n-1;
  171.                 ans = *it;
  172.             }
  173.             cout<<ans<<endl;
  174.             continue;  
  175.         }
  176.         vector <ll>::iterator it;
  177.         ll id;
  178.         F(i,0,4)
  179.         {
  180.             if(primes[i] == k)
  181.                 id = i;
  182.         }
  183.         it = lower_bound(arr[id].begin(),arr[id].end(),a);
  184.         if(*it == a)
  185.         {
  186.             it = it + n-2;
  187.             ans = *it;
  188.         }
  189.         else
  190.         {
  191.             //debug(*it);
  192.             it = it + n-1;
  193.             ans = *it;
  194.         }
  195.         cout<<ans<<endl;
  196.     }
  197.     return 0;
  198. }
RAW Paste Data Copied