Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define fastIO std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
- using namespace std;
- int phi[1100000];
- int cntArr[1000001];
- void phiSieve(int n)
- {
- int i,j,k,temp,tempB;
- int cnt =0;
- for(i=1; i<=n; i++)
- {
- phi[i]=i;
- }
- for(i=2; i<=n; i++)
- {
- if(phi[i]==i)
- {
- phi[i]=i-1;
- for(j=i*2; j<=n; j+=i)
- {
- phi[j] = phi[j]/i*(i-1);
- }
- }
- }
- for(i=2; i<=n; i++)
- cntArr[i] += cntArr[phi[i]]+1;
- }
- }
- int main()
- {
- int n,i,t,a,b,k;
- phiSieve(1000000);
- int cnt2 =0;
- fastIO;
- scanf("%d",&t);
- while(t--)
- {
- scanf("%d %d %d",&a,&b,&k);
- cnt2=0;
- for(i=a; i<=b; i++)
- {
- if(cntArr[i]==k)
- {
- cnt2++;
- }
- }
- printf("%d\n",cnt2);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement