Round B APAC Test 2017 , Problem B: Sherlock and Watson Gym Secrets

If any one have solved this question ,then please share the approach to solve the problem

1 Like

Simple case: consider A and B as 1

From 1 to n each number has a remainder with k in the range of 0 to k-1.
this pattern of remainders is repeating i.e. [1,2,…0][1,2,…0] with last block as some prefix of the such a blovk
example for n=7 k = 3 the remainders with 3 are [1 2 0][1 2 0][1].So store the count of each remainder in an array of size k. where

arr[i] = n/k + (n%k>=i) 0<=i<=k-1

the n%k>=i is the part of the last block

Now if we consider a and b as not equal to 1, we see that there will still be a pattern in blocks of size k(why? ) but the pattern will not be [1,2…0]. eg N=8,a = 2,k = 3
pattern is [1,1,0][1,1,0][1,1]
iterate from i = 1 to k. find the value i^a mod k.

cntA[i^a mod k] += n/k + (n%k>=i).

Similarly for b also;

ans = sum(i = 0 to k-1 (cntA[i]*cntb[k-i]);

Ofcourse you must also take care for repeating numbers(i.e. i=j) and corner cases.


**I was only able to clear the small input case. **

Method: Brute force

What I did was, run nested loops(i,j) and compare if power(i,a)(mod k) + power(j,b)(mod k) was divisible by k. If it was divisible then I updated the counter variable.

1 Like