CHFING not working for subtask2

please find the error, why it is not working for subtask2
Here is the link code

Well, your code shows different output when compared with my code:
Input: N= 2[fixed] & varying from K = 10^10 to k = 10 ^18
Your Output: for N = 2, K = 10^10 is 544142479
Mine: 2485 :wink:
Similarly, with
Inputs Like : N = 2, K = 10^11
Your output: 185020288
Mine: 245350, Maybe I got Lucky here
PLEASE Correct me if I’m wrong. Here is my AC code :slight_smile: https://www.codechef.com/viewsolution/24647123

Hey!
Can you please explain your code. A little explanation on how do you come up with this algorithm will work.

Idea: Consider N = 2 and K = 100, so we have to use the values that are in the range [100, 101] and find out the total number of values that are unreachable. The values that are lower than K are definitely unreachable, here the values {1,2,3,4,5,6,…99} are unreachable. (i. e nothing but (K - 1) number of values = (100 - 1) = 99). Now, moving onto values that are greater than K and lower than second multiple of K( K * 2 = 100 * 2 = 200) , here in this case {102, 103, 104, 105,106,…199} are unreachable. (these are 98 in total). Now, moving onto values that are lower than 3rd multiple of K which is nothing but (K * 3 = 100 * 3 = 300) , we have {203, 204, 205, … 299) values are unreachable(97 in total). It following a pattern of AP Series with last term as 99 having a common difference between the numbers as 1.
Pattern = 99 + 98 + 97 + …1
Well, the first term may differ according with the case that involves, here the first term a = 1;
No. Of terms here = n = 99
So, the sum formula = n/2(2a + (n - 1)d) = 4950 (in this case) ;
Generalizing all the cases:
Pattern : a, a + d, a + 2
d, a + 3*d, … a + (n-1)*d.
Last Term = K - 1;
Difference d = (N + K - 1) - K = N - 1;
No of terms (n) = Last term / Difference = L / d;
First Term a = Last Term - (No.of terms - 1) * Common difference = L - (n - 1)*d;
Sum(No. of Unreachable Values) = (No .of Terms * a) + (1 + 2 + 3 + 4+…(no. of terms - 1)) * Common difference;
we know that : 1 + 2 + 3 +… n - 1 terms sum is nothing but (n * (n-1)) / 2;
Lets suppose this sum be j, therefore j = (n * (n-1))/2;
Therefore, Sum(No. of unreachable Values) = (n * a) + (j * d); :smile:
That’s it We are Done !
Hope it helps.
NOTE : N is Given input , n is no .of terms
Thank you!

1 Like

In your code in line number 28 the formula is not correct. (a/b)%m is not equal to ((a%m)/(b/%m))%m. But instead it should be ((a%m)*((b^-1)%m)%m)%m , where b^-1 is the multiiplicative modulo inverse of b with m. I guess you got lucky here.

Yeah, I’ve actually forgotten to remove the %m after ‘/2’. But It works in both the cases(removal of %m and non removal of %m after ‘/2’). Thanks for Pointing out ! :sweat_smile: