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
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 CodeChef: Practical coding for everyone
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 + 2d, 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);
That’s it We are Done !
Hope it helps.
NOTE : N is Given input , n is no .of terms
Thank you!
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 !