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.
3 Likes
**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