• API
• FAQ
• Tools
• Archive
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.

Top