SHARE
TWEET

Untitled

a guest Oct 18th, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <set>
  2. #include <map>
  3. #include <cmath>
  4. #include <deque>
  5. #include <queue>
  6. #include <vector>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <algorithm>
  10. using namespace std;
  11. #define x first
  12. #define y second
  13. #define pb push_back
  14. #define pf push_front
  15. #define ppb pop_back
  16. #define ppf pop_front
  17. #define ll long long
  18. #define ld long double
  19. #define ii pair<int,int>
  20. #define fall(a,c) for(auto &a:c)
  21. #define all(k) k.begin(),k.end()
  22. #define rall(k) rbegin(k),rend(k)
  23. #define heap priority_queue
  24. #define endl '\n'
  25.  
  26. const int P = 2e6+5;
  27. vector<ll> phi(P+1);
  28. void PHI(){//get prime factors and calculate phi
  29.     for(ll i=1;i<P;i++)phi[i]=i;
  30.     for(ll i=2;i<P;i++){//O(N)
  31.         if(phi[i]==i){//n is prime
  32.             for(ll j=i;j<P;j+=i){//O(logi)
  33.                 //i is a prime factor of j
  34.                 phi[j]=phi[j]/i*(i-1);
  35.             }
  36.         }
  37.     }
  38. }
  39.  
  40. ll memo[P];
  41. ll depth(ll n){
  42.     if(n==1) return 0;
  43.     if(memo[n]!=-1) return memo[n];
  44.     return memo[n] = 1+depth(phi[n]);
  45. }
  46. vector<ll> sk[20];
  47.  
  48. #define endl '\n'
  49. int32_t main(){
  50.     ios::sync_with_stdio(0); cin.tie(0);
  51.     PHI();
  52.     memset(memo, -1, sizeof memo);
  53.     int t; cin>>t;
  54.     for(int i=1;i<=1000000;i++){
  55.         if(depth(i)<20)
  56.             sk[depth(i)].pb(i);
  57.     }
  58.  
  59.  
  60.     while(t--){
  61.         int n,m,k;
  62.         cin>>m>>n>>k;
  63.         auto ans = int(upper_bound(all(sk[k]),n)-sk[k].begin()) - int(lower_bound(all(sk[k]),m)-sk[k].begin());
  64.         cout<<ans<<endl;
  65.     }
  66.  
  67.  
  68.  
  69.     return 0;
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top