SPOJ Q&A

#include<stdio.h>
#define max 100001
#define ull long long int
int pre[max][11];
void presolve()
{
int i,j,temp,k;
for(i=2;i*i<max;i++)
{
if(pre[i][10])
continue;
k=i*i;
for(j=k;j<max;j+=k)
{
if(pre[j][10]==0)
pre[j][10]=1;
}
}

for(i=0;i<max;i++)
{
if(pre[i][10]==0)
{
temp=i;
while(temp)
{
pre[i][temp%10]=1;
temp/=10;
}
}
}
for(i=1;i<max;i++)
{
for(j=0;j<=9;j++)
pre[i][j]+=pre[i-1][j];
}

}

int main()
{
int t,a,b,d;
scanf("%d",&t);
presolve();
while(t--)
{
scanf("%d%d%d",&a,&b,&d);
printf("%d\n",pre[b][d]-pre[a-1][d]);
}
}

Hackerearth QAS

                   Baba & Guruji

Baba wants to kill Guruji. He has a master plan but Guruji is prepared for him.

Baba released a bacterial concentration of 1 unit in Guruji's underground water source on Day 0. The concentration of bacteria becomes xtimes the concentration day before. But,Guruji's powder kills y units of bacteria each day, starting from Day 1.

Guruji needs your help to estimate the concentration of bacteria on the N th day.

Note : Large Input/Output Data. Use fast I/O.

Input :

First line consists of 2 space separated integers x and y. The next line consists of a single integer Q, denoting the number of queries Guruji has for you. The next Q lines are such that each line consists of a single integer N.

Output :

For each query of Guruji, print the number of bacteria present on the N th day on a new line. Since the answer can be really huge, print the answer modulo 1000000007 (10^9 + 7) .

Constraints :

2<=x<=100

0<=y<=(x-2)

1<=Q<=10^6

1<=N<=10^6

1. #include<iostream>
2. #include<cstdio>
3. #include<string>
4. #define ull long long int
5. using namespace std;
6. #define max 1000001
7. #define mod 1000000007
8. ull conc[max];
9. void pre(int x,int y)
10. {
11.  conc[0]=1;
12.  for(int i=1;i<max;i++)
13.     {
14.       conc[i]=(conc[i-1]*x)%mod-y;
15.     }
16. }
17. int main()
18. {
19.     int x,y;
20.     int Q,N;
21.     scanf("%d",&x);
22.     scanf("%d",&y);
23.     scanf("%d",&Q);
24.     pre(x,y);
25.     for(int j=0;j<Q;j++)
26.     {
27.      scanf("%d",&N);
28.      printf("%d\n",conc[N]%mod);
29.     }
30. }