MATNUM - Divisibility Test
Problem statement is simple and straight forward. You will be given a non-negative integer P of length N and you need to check whether it's divisible by Q?
Integer P will be given in its decimal representation with P0 as leftmost digit and P1 as second digit from left!
Rest of the digit can be generated from the formula:
Pi = (4*Pi-1 + Pi-2) modulo Q for 2 <= i <= N-1
Input
The first line contains one integer T - denoting the number of test cases.
T lines follow each containing four integers P0, P1, Q and N!
Output
For each testcase output YES if the corresponding integer is divisible by Q and NO otherwise.
Constraints
- T <= 100000
- 0 < P0, P1, Q < 10
- 0 < N <= 1018
Example
Input: 4 1 4 2 2 1 4 2 1 4 2 3 2 3 4 7 3 Output: YES NO YES NO
Explanation
Value of P is 14, 1, 42, 345 in respective cases !
hide comments
David:
2021-12-14 18:54:30
Some have asked for additional test cases. This is very unlikely to provide help. Each combination of p0, p1, and q must be examined. In some cases, a specific combination of p0, p1, and q has several conditions on which n is divisible. |
|
nadstratosfer:
2018-04-28 04:41:43
This problem ruined the Friday night for my wife... but was totally worth it =) Big thumbs up for this beauty! |
|
:D:
2016-10-17 14:50:36
Problem seems very basic, but it's fun to solve and optimize. Thanks to the author. |
|
raj_jha:
2016-06-16 09:21:18
can u tell me why i am getting wrong answer
|
|
gomathi ganesan:
2015-12-31 07:37:51
Some more test cases....pls.. |
|
DHEERAJ KUMAR:
2015-12-25 11:30:09
@Adk can u tell me why am i getting WA?? submission id: 15937639 |
|
Advitiya:
2015-12-17 23:49:11
what's wrong with my solution id=15888473 :( |
|
shally darbari:
2015-12-09 11:23:18
can u tell me why i am getting wa?? submission id is :15812896
|
|
Bhuvnesh Jain:
2015-11-30 21:56:35
@adarsh kumar, can you please tell me why I am getting WA as I have tested by code on random test cases with brute solution as well and it was working fine... my last solution contains comments showing the implementation details and logic of solution as well.
|
|
Bhuvnesh Jain:
2015-11-30 16:46:44
Are the submissions being rejudged?
|
Added by: | Adarsh kumar |
Date: | 2015-11-29 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | Own problem |