I am now getting WA... will try to implement O(1) soln if this cannot be corrected.
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<iostream>
#define MAX 1000001
using namespace std;
int prime_factor[MAX];int tau[MAX];
int vec_bsearcha(vector<int> &v,int a){
int mid;
int first=0,last=v.size()-1;
while(first<=last){
mid=(first+last)/2;
if(a==v[mid]) return mid;
else if(a<v[mid]) last=mid-1;
else first=mid+1;
}
return mid;
}
int vec_bsearchb(vector<int> &v,int a){
int first=0,last=v.size()-1;
int mid;
while(first<=last){
mid=(first+last)/2;
if(a==v[mid]) return mid;
else if(a<v[mid]) last=mid-1;
else first=mid+1;
}
return mid-1;
}
int main()
{
int i,j;
for(i = 1; i <= MAX-1; i++) {
prime_factor[i] = i;
//tau[i]=0;
}
for(i = 2; i <= MAX-1; i++){
if(prime_factor[i] == i){
tau[i]++;
for(j = i+i; j <= MAX-1; j+=i)
{prime_factor[j]=i; tau[j]++;}
}
}
//display(tau);
vector<int>v[11];
for(i=0;i<=MAX-1;i++){
switch(tau[i]){
case 0: v[0].push_back(i); break;
case 1: v[1].push_back(i); break;
case 2: v[2].push_back(i); break;
case 3: v[3].push_back(i); break;
case 4: v[4].push_back(i); break;
case 5: v[5].push_back(i); break;
case 6: v[6].push_back(i); break;
case 7: v[7].push_back(i); break;
case 8: v[8].push_back(i); break;
case 9: v[9].push_back(i); break;
case 10:v[10].push_back(i); break;
}
}
int T;
int a,b,n,count=0;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&a,&b,&n);
int x2=vec_bsearchb(v[n],b);
int x1=vec_bsearcha(v[n],a);
if(a==1 && n==0) printf("%d\n",1);
else if(x2==x1) printf("%d\n",0);
else printf("%d\n",x2 - x1 + 1);
/*while(a<=b){
if(tau[a]==n) count++;
a++;
}
printf("%d\n",count);
count=0;*/
}
return 0;
}
