fork download
copy 
  1. /**
  2.  *  winners never quit
  3. **/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. const int N = 1e8;
  9.  
  10. long long mod = 1e9 + 7;
  11.  
  12. long long power(long long b, long long p){
  13.   if (p==0)return 1LL % mod;
  14.   if (p%2)return ((power(b, p-1)%mod) * (b%mod)) % mod;
  15.   long long m = power(b, p/2);
  16.   return ((m%mod)*(m%mod)) % mod;
  17. }
  18.  
  19. vector <bool> mark(N+1, false);
  20. vector <int> prime;
  21.  
  22. void sieve(){
  23.   prime.push_back(2);
  24.   for (long long i = 3;i <= N;i += 2){
  25.     if (mark[i])continue;
  26.     prime.push_back(i);
  27.     for (long long j = i*i;j <= N;j += i+i){
  28.       mark[j] = true;
  29.     }
  30.   }
  31. }
  32.  
  33. vector <pair <long long, int> > pd;
  34.  
  35. void prime_div(long long n){
  36.   for (int i = 0;i < prime.size();i++){
  37.     long long temp = prime[i];
  38.     if (temp*temp > n)break;
  39.     if (n%temp==0){
  40.       int cnt = 0;
  41.       while (n%temp==0){
  42.         n /= temp;
  43.         cnt++;
  44.       }
  45.       pd.push_back({temp, cnt});
  46.     }
  47.   }
  48.   if (n > 1)pd.push_back({n, 1});
  49. }
  50.  
  51. vector <long long> all_div;
  52.  
  53. void find_all(){
  54.   vector <long long> di;
  55.   for (int i = 0;i < pd.size();i++){
  56.     for (int j = 0;j < pd[i].second;j++){
  57.       di.push_back(pd[i].first);
  58.     }
  59.   }
  60.   int len = (1 << di.size());
  61.   map <long long, int> mp;
  62.   for (int i = 0;i < len;i++){
  63.     long long cur = 1;
  64.     for (int j = 0;j < di.size();j++){
  65.       if (i & (1<<j))cur *= di[j];
  66.     }
  67.     if (!mp[cur])all_div.push_back(cur);
  68.     mp[cur]++;
  69.   }
  70. }
  71.  
  72. int main()
  73. {
  74.   ios::sync_with_stdio(0);
  75.   cin.tie(0);
  76.   int tc, ca = 0;
  77.   sieve();
  78.   cin >> tc;
  79.   while (tc--){
  80.     long long n, k;
  81.     cin >> n >> k;
  82.     prime_div(n);
  83.     find_all();
  84.     long long ans = 0;
  85.     for (int i = 0;i < all_div.size();i++){
  86.       ans = ((ans%mod) + power(all_div[i], k)) % mod;
  87.     }
  88.     cout << ans << '\n';
  89.     pd.clear();
  90.     all_div.clear();
  91.   }
  92.   return 0;
  93. }
Time limit exceeded #stdin #stdout 5s 48456KB
comments (?)
stdin
copy 
1
1073741824 11
stdout
copy 
Standard output is empty
https://ideone.com/fOkxxp
language:
C++14 (gcc 8.3)
created:
5 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!