http://spoj.com/problems/CPU
The idea is to generate all possible numbers and then binary search to find the result.
Ive checked the generated numbers with that of OEIS and it shows the same but still im getting WA.
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
#define ll long long
#define pb push_back
#define MAX 1000000
int sieve[1000100];
int makesieve(){
int i,j;
for(i=2;i<=1000;i++){
if(!sieve[i]){
for(j=i*i;j<=MAX;j+=i){
sieve[j]=1;
}
}
}
}
int a,b,maxN;
ll sofar;
ll check(int l,int prev){
if(l==maxN) return sofar;
ll x=a*prev+b;
if(x<0 || sofar>=2000000000 || x>=1000000 || sieve[x]){
return sofar=0;
}
sofar*=x;
return check(l+1,x);
}
vector<int> soln(243);
int solve(){
int i,j,n,x,k=0;
for(i=1;i<=1000;i++){
for(j=-1000;j<=1000;j++){
if(j!=0)
for(n=3;n<=20;n++){
sofar=1,a=i,b=j,maxN=n;
check(0,1);
if(sofar>1 && sofar<=2000000000)
soln[k++]=sofar;
}
}
}
sort(soln.begin(),soln.end());
}
int main(){
makesieve();
solve();
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&a,&b);
if(a>b) a^=b^=a^=b;
a--;
printf("%d\n",lower_bound(soln.begin(),soln.end(),b)-lower_bound(soln.begin(),soln.end(),a));
}
return 0;
}
