May you help me pleas?

Question

You are given a huge positive integer A. It is guaranteed that this number has no leading ZEROS.
You can perform two types of operations using some given key value K (a positive integer):
1. You can add any multiple of K to A. (A = (A + K ∗ X), whereX = 0, 1, 2, 3, 4, 5. . . . . .)
2. You can subtract any multiple of K from A. (A = (A − K ∗ X), whereX = 0, 1, 2, 3, 4, 5. . . . . .)
Your friend believes that the pair (A, K) is beautiful if you can make A become ZERO
through performing the previous operations only.
Find out if a given Pair (A, K) is beautiful pair or not.
Input
The first line contains a single integer T denoting the number of test cases.
The first input line of each test case contains a huge Integer A (1 ≤ |A| ≤ 105
) where |A| is the length of
the integer A.
The second line contains an integer K (1 ≤ K ≤ 109
) denoting the key value.
Output
For each test case, print "YES"(without the quotes) if the pair (A, K) is beautiful. Otherwise, print "NO".

Answer 1

Hi Morsai! Can you show us your attempts at solving this problem? It will help us identify where you are stuck, so that we can more effectively help you.

Answer 2

Thanks a lot , i actually couldn't understand what to do .

Answer 3

My basic understanding is you will be given some pair of values, A and K. A is very big, and can go up to 105 digits (that's like, 10 to the power of 105). K is much smaller, its value ranging only from 1 to 109. You need to identify if the pair is "beautiful".

"Beautiful" in this case means that you can perform one of these operations on A until A becomes zero.

A = (A + K ∗ X)
A = (A - K ∗ X)

where X is zero or any positive integer. So far example, let's say A is 10000 is K is 50, we say this pair is beautiful because, when X is 200,

10000 - (50 * 200) = 0.

In a different case, if A is 10001 and K is 50, you can never get A to become zero no matter how you change X.

Answer 4

If you understand the problem now based on my explanation, it should makes sense to you that the answer to the problem can be summed up in one condition:

If A can be divided by K without any remainder, the pair (A, K) is beautiful, else, (A,K) is not beautiful.

The roadblock is that A is very large! Is there a way to find out the quotient and remainder of big numbers? The answer is yes:

https://www.geeksforgeeks.org/program-quotient-remainder-big-number/