Contest link: Intra AUST Preliminary Fall - 17
Problem name: Even the Odds!
Required knowledge: Modular arithmetic, big multiplication.
Editorial: Firstly, try reading this Modular Arithmetic or you can google about modular arithmatic and it's properties. Now let's analyze the problem.
Given N and M, we need to find summation of first N even numbers modulo M and summation of first N odd numbers modulo M.
We can observe that the first N odd numbers summation can be found by calculating N * N and first N even numbers summation can be found by calculating N * (N+1).
let, N = 4,
Odd : 1 + 3 + 5 + 7 = 16 = 4 * 4
Even : 2 + 4 + 6 + 8 = 20 = 4 * 5
As the modulo M is really big we can't simply calculate ( (N % M) * ( (N+1)%M) )%M, because the N can be as large as 1018 - 1 and M can be 1018, then at the time of multiplying, it will overflow. How can we do this without overflow? We will simply use a divide and conquer technique to calculate N * N by adding N with N, N times, instead of multiplying them. Let N = 1018 - 1, M = 1018.
Now, from modular arithmatic we know that
- (a * b) % m = (( a%m ) * ( b%m ))%m
- (a + b) % m = (( a%m ) + ( b%m ))%m
Say, a = 1018 and b = 10 and m = 1018 - 1.
So, ( (1018 - 1) %1018 ) * (1018 - 1) %1018 ) ) % 1018= ( (1018 - 1) * (1018 - 1) ) % 1018 = 0 ; here (1018 - 1) * (1018 - 1) will cause overflow.
But,(((1018 - 1)%1018) + ((1018 - 1)%1018) + ....
We can easily add (1018 - 1 + 1018 - 1) and then mod it with 1018. We will do this 1018 times, and by using modulo operation each time, there won't be any overflow.
As 1018 is also a very big number, we can do this is O (log10(N)) times with folowing divide and conquer algorithm.
We will use this bigmul function to calculate ( a * b ) % c. We will simply add the number a, b times each with modulo operation. As the range is too big, we can't simply use loop, so we will use this recursion technique of calculating big multiplication in logN time.
Problem name: Even the Odds!
Required knowledge: Modular arithmetic, big multiplication.
Editorial: Firstly, try reading this Modular Arithmetic or you can google about modular arithmatic and it's properties. Now let's analyze the problem.
Given N and M, we need to find summation of first N even numbers modulo M and summation of first N odd numbers modulo M.
We can observe that the first N odd numbers summation can be found by calculating N * N and first N even numbers summation can be found by calculating N * (N+1).
let, N = 4,
Odd : 1 + 3 + 5 + 7 = 16 = 4 * 4
Even : 2 + 4 + 6 + 8 = 20 = 4 * 5
As the modulo M is really big we can't simply calculate ( (N % M) * ( (N+1)%M) )%M, because the N can be as large as 1018 - 1 and M can be 1018, then at the time of multiplying, it will overflow. How can we do this without overflow? We will simply use a divide and conquer technique to calculate N * N by adding N with N, N times, instead of multiplying them. Let N = 1018 - 1, M = 1018.
Now, from modular arithmatic we know that
- (a * b) % m = (( a%m ) * ( b%m ))%m
- (a + b) % m = (( a%m ) + ( b%m ))%m
Say, a = 1018 and b = 10 and m = 1018 - 1.
So, ( (1018 - 1) %1018 ) * (1018 - 1) %1018 ) ) % 1018= ( (1018 - 1) * (1018 - 1) ) % 1018 = 0 ; here (1018 - 1) * (1018 - 1) will cause overflow.
But,(((1018 - 1)%1018) + ((1018 - 1)%1018) + ....
We can easily add (1018 - 1 + 1018 - 1) and then mod it with 1018. We will do this 1018 times, and by using modulo operation each time, there won't be any overflow.
As 1018 is also a very big number, we can do this is O (log10(N)) times with folowing divide and conquer algorithm.
We will use this bigmul function to calculate ( a * b ) % c. We will simply add the number a, b times each with modulo operation. As the range is too big, we can't simply use loop, so we will use this recursion technique of calculating big multiplication in logN time.
