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
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 !
For each testcase output YES if the corresponding integer is divisible by Q and NO otherwise.
- T <= 100000
- 0 < P0 , P1 , Q < 10
- 0 < N <= 1018
Input: 4 1 4 2 2 1 4 2 1 4 2 3 2 3 4 7 3 Output: YES NO YES NO
Value of P is 14, 1, 42, 345 in respective cases !
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.
This problem ruined the Friday night for my wife... but was totally worth it =) Big thumbs up for this beauty!
Problem seems very basic, but it's fun to solve and optimize. Thanks to the author.
can u tell me why i am getting wrong answer
Some more test cases....pls..
@Adk can u tell me why am i getting WA?? submission id: 15937639
what's wrong with my solution id=15888473 :(
can u tell me why i am getting wa?? submission id is :15812896
@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.
Are the submissions being rejudged?