erfanul007

LOJ 1340

Sep 15th, 2021
559
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #ifdef ERFANUL007
  6.     #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
  7.     template < typename Arg1 >
  8.     void __f(const char* name, Arg1&& arg1){
  9.         cout << name << " = " << arg1 << std::endl;
  10.     }
  11.     template < typename Arg1, typename... Args>
  12.     void __f(const char* names, Arg1&& arg1, Args&&... args){
  13.         const char* comma = strchr(names, ',');
  14.         cout.write(names, comma - names) << " = " << arg1 <<" | ";
  15.         __f(comma+1, args...);
  16.     }
  17. #else
  18.     #define debug(...)
  19. #endif
  20.  
  21. #define ll long long int
  22.  
  23. template <class T> inline T bigMod(T p,T e,T M){T ret=1; for(;e>0;e>>=1){ if(e&1) ret=(ret*p)%M; p=(p*p)%M;} return (T)ret;}
  24.  
  25. const int N = 100000;
  26. const ll Mod = 10000019;
  27.  
  28. bool isprime[N + 2];
  29. vector< int > prime;
  30.  
  31. void sieve(){
  32.     memset(isprime, 1, sizeof(isprime));
  33.     for(int i=4; i<=N; i+=2) isprime[i] = 0;
  34.     for(int i=3; i*i<=N; i+=2){
  35.         if(!isprime[i]) continue;
  36.         for(int j=i*i; j<=N; j+=(i*2)){
  37.             isprime[j] = 0;
  38.         }
  39.     }
  40.     prime.push_back(2);
  41.     for(int i=3; i<=N; i+=2){
  42.         if(isprime[i]) prime.push_back(i);
  43.     }
  44. }
  45.  
  46. int primecnt(int n, int p){
  47.     int cnt = 0;
  48.     while(n){
  49.         cnt += (n/p);
  50.         n/=p;
  51.     }
  52.     return cnt;
  53. }
  54.  
  55. ll getans(int n, int k){
  56.     ll ans = 1;
  57.     for(int i=0; i<prime.size() && prime[i]<=n; i++){
  58.         int cnt = primecnt(n, prime[i]);
  59.         if(cnt < k) continue;
  60.         ll p = cnt/k;
  61.         ans = (ans * bigMod((ll)prime[i], p, Mod)) % Mod;
  62.         //debug(prime[i], p, ans);
  63.     }
  64.     if(ans == 1) return -1;
  65.     return ans;
  66. }
  67.  
  68. int main(){
  69.     #ifdef ERFANUL007
  70.         clock_t tStart = clock();
  71.         freopen("input.txt", "r", stdin);
  72.         freopen("output.txt", "w", stdout);
  73.     #endif
  74.  
  75.     sieve();
  76.  
  77.     int t, cs=0;
  78.     cin >> t;
  79.  
  80.     while(t--){
  81.         int n, k;
  82.         cin >> n >> k;
  83.         int ans = getans(n, k);
  84.         cout << "Case " << ++cs << ": ";
  85.         cout << ans << '\n';
  86.     }
  87.  
  88.     #ifdef ERFANUL007
  89.         fprintf(stderr, ">>> Runtime : %.9f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  90.     #endif
  91.  
  92.     return 0;
  93. }
RAW Paste Data