Lucky Days

Problem code: LUCKYDAY

All submissions for this problem are available.

Chef Ciel defined a sequence S as follows:
S[1] = A
S[2] = B
S[i] = (X*S[i-1] + Y*S[i-2] + Z) mod P, for i >= 3

Ciel considers C is a lucky number, and the i-th day is a lucky day if and only if S[i] = C. Ciel's restaurant may have special events in a lucky day.

By the way, your work is calculating the numbers of lucky days in intervals. That is, for each Q intervals [L[i], R[i]], you should calculate the number of the integers k which satisfy L[i] <= k <= R[i] and S[k] = C.

Input

The first line contains an integer T, the number of test cases. Then T test cases follow. The first line for each test case has 8 integers A, B, X, Y, Z, P, C and Q. The next Q lines have 2 integers L[i] and R[i].

Output

For each interval, print the number of lucky days in the interval.

Constraints

1 <= T <= 2
2 <= P <= 10007
P is a prime.
0 <= A, B, X, Y, Z, C < P
1 <= Q <= 20000 (2*10^4)
1 <= L[i] <= R[i] <= 1000000000000000000 (10^18)

Sample Input

2
1 1 1 1 0 2 0 6
1 1
2 2
3 3
4 4
5 5
6 6
1 2 4 5 3 17 4 3
5 8
5 58
58 5858

Sample Output

0
0
1
0
0
1
0
4
362

Output details

In the first case:
S[1] = A = 1
S[2] = B = 1
S[3] = (S[2] + S[1]) mod 2 = (1 + 1) mod 2 = 0
S[4] = (S[3] + S[2]) mod 2 = (0 + 1) mod 2 = 1
S[5] = (S[4] + S[3]) mod 2 = (1 + 0) mod 2 = 1
S[6] = (S[5] + S[4]) mod 2 = (1 + 1) mod 2 = 0
S[7] = (S[6] + S[5]) mod 2 = (0 + 1) mod 2 = 1

Author: laycurse
Tester: chmel_tolstiy
Editorial http://discuss.codechef.com/problems/LUCKYDAY
Date Added: 1-10-2011
Time Limit: 5 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Should we consider number P

lutyj @ 1 Nov 2011 04:51 PM
Should we consider number P to be prime?

Oops. Found it in the text.

lutyj @ 1 Nov 2011 04:54 PM
Oops. Found it in the text.

For: 1 2 4 5 3 17 4 3 5 8 5

mayank.punetha @ 2 Nov 2011 12:23 AM
For: 1 2 4 5 3 17 4 3 5 8 5 58 58 5858 shouldn't the output for 5-58 be 3??

sorry my mistake!!

mayank.punetha @ 2 Nov 2011 01:44 AM
sorry my mistake!!

3 correct "JAVA" submissions,

pragrame @ 2 Nov 2011 05:16 PM
3 correct "JAVA" submissions, and 0 "C++" (so far). This must be a first! :P

My code exits with runtime

gurpreet_09 @ 2 Nov 2011 11:52 PM
My code exits with runtime error code "Other". Can anybody please tell me what kind of mistake might cause this error.

do we have to print the

abhi922 @ 4 Nov 2011 12:00 AM
do we have to print the number of lucky days for each L[i] and R[i] simultaneously or print all the values of the number of lucky days at the end?

@admin i am getting a runtime

redstar @ 4 Nov 2011 06:01 PM
@admin i am getting a runtime error can u see my code and tell me which test case it is failing

Can X,Y and Z be negative

chandransuraj @ 4 Nov 2011 11:15 PM
Can X,Y and Z be negative integers?

@chandransuraj if they are

redstar @ 4 Nov 2011 11:31 PM
@chandransuraj if they are negative then all values in s[ i ] are negative and simply you get zero for every case.....

@chandansuraj - carefully

shettynamit @ 5 Nov 2011 02:11 AM
@chandansuraj - carefully read the CONSTRAINTS section of the question, its clearly mentioned that A,B,C,X,Y,Z are all greater than or equal to 0

Thanks a lot guys...my bad

chandransuraj @ 6 Nov 2011 05:05 PM
Thanks a lot guys...my bad

am I missing something or the

theicebreaker @ 8 Nov 2011 04:39 PM
am I missing something or the interval lengths are within certain limits. like R[i] -L[i] <= ????

theicebreaker: The limits are

tomek @ 8 Nov 2011 11:26 PM
theicebreaker: The limits are in the Constraints section.

hi guys. i'm printing some

bela_mervado @ 11 Nov 2011 04:13 AM
hi guys. i'm printing some junk just before return 0; in my main(). i get WA this way, at 0.21s . without this printf i get TL. wtf??

SUCCESSFUL SUBMISSIONS


Fetching successful submissions