Question on number theory

general
1

plz help in this question.

The statement of this problem is very simple: you are given a non-negative integer X. Whether it's divisible by 41?

Input
The first line contains one integer T - denoting the number of test cases. The following T lines contain 4 integers a[0], a1, c, n each and describe each test case:

Let's consider decimal representation of the number X as an array where a[0] is the leftmost (highest) digit. You are given a[0], a1 and each a[i] for 2 <= i <= n-1 can be found by formula:

a[i] = ( a[i - 1]*c + a[i - 2] ) modulo 10

Output
For each test case output YES if the corresponding integer is divisible by 41 and NO otherwise.

Constraints

T <= 2000
1 <=N <= 50000
0 <= a[0], a1, c < 10

Do i really need to find all the digits of the number to checks the divisiblity by 41…?? any better approach then finding all the digits seperately and then dividing would be appriciated.

2

You definitely need to compute all digits. No matter what you divide by (unless it’s 1) you always have to check at least the last digit.

Concerning “dividing” the resulting number: You can do the divisibility test iteratively: Start with m=a[0]%41 (this is obviously a[0]) and go through all numbers i>0 with m=(10*m+a[i])%41. In the end m will be zero if and only if a is divisible by 41.

This algorithm can pass. In order to speed it up, you can use the fact that you’re computing a lot of expressions x%10 and x%41 where x is at most a three-digit number. You can replace these computations by using a precomputed look-up table.

3

thanks @ceilks :slight_smile: