fork download
copy 
  1. #include<unordered_map>
  2. #include<unordered_set>
  3. #include<functional>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<hash_map>
  7. #include<iterator>
  8. #include<iomanip>
  9. #include<numeric>
  10. #include<cstring>
  11. #include<vector>
  12. #include<string>
  13. #include<deque>
  14. #include<stack>
  15. #include<queue>
  16. #include<array>
  17. #include<cmath>
  18. #include<list>
  19. #include<map>
  20. #include<set>
  21. using namespace std;
  22. typedef long long ll;
  23. typedef unsigned long long ull;
  24. typedef double db;
  25. #define pii pair<int,int>
  26. #define pll pair<ll,ll>
  27. #define inf INT32_MAX
  28. #define linf INT64_MAX
  29. #define pf push_front
  30. #define pb push_back
  31. #define ppb pop_back
  32. #define ppf pop_front
  33. #define ff first
  34. #define ss second
  35. const int mod=1e9+7,N=5e4;
  36. ll Pow(ll b,ll p){
  37.     if(!p)return 1%mod;
  38.     if(p==1)return b%mod;
  39.     ll tmp=Pow(b,p/2)%mod;
  40.     tmp=(tmp*tmp)%mod;
  41.     if(p&1)tmp=(tmp*b)%mod;
  42.     return tmp%mod;
  43. }
  44. ll calcLog(ll n,ll b){
  45.     ll cnt=0;
  46.     while(n>=b)cnt++,n/=b;
  47.     return cnt;
  48. }
  49. bool solve(){
  50.     ll x,n,ans=1;
  51.     cin>>x>>n;
  52.  
  53.     set<ll>s;
  54.     for(ll i=2;i*i<=x;++i){
  55.         while(x%i==0){
  56.             s.insert(i),x/=i;
  57.         }
  58.     }
  59.     if(x>1)s.insert(x);
  60.  
  61.     for(const auto &i:s){
  62.         ll prev=n/i,cur,prevBase=1,curBase=2,log=calcLog(n,i);
  63.         while(prevBase<=log){
  64.             cur=n/Pow(i,curBase);
  65.             prev-=cur;
  66.             ans=(ans*Pow(i,prevBase*prev))%mod;
  67.             prev=cur;
  68.             prevBase++,curBase++;
  69.         }
  70.     }
  71.     cout<<ans;
  72. }
  73. int main(){
  74.     //ios_base::sync_with_stdio(false);
  75.     //cin.tie(nullptr);
  76.     int t=1;
  77.     //cin>>t;
  78.     while(t--){
  79.         solve();
  80.     }
  81. }
Runtime error #stdin #stdout 0s 5660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tkQZ4L
language:
C++14 (gcc 8.3)
created:
2 years 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!