Strange combination I know but here is my question: We have 0 <= k <= n < 500000. We need create an anlogithm that calculute Euler function of C(n, k) and not spend all your life for it)). Print the result of Euler function of C(n, k) mod 1000000007 (means phi(C(n, k)) % 1000000007 ).
I tried it a few times, but unfortunately I could make something good only for n <= 50000. I had a few approaches, but some of them I couldn't implement properly.
Euler function is multiplicative for relatively primes, and futher more you can easily calculate it if you get all prime numbers of N. So I tried the factorization of C(n, k) and failed. I know only algorithm of factorization with O(N^0.5), so it took too much time. I read about other factorization algorithms, but their complexity was only about O(N^0.25). I think it is not enough.
Then I learned that Euler function can be multiplicative even for numbers with GCD > 1 but it needs correction. Here is how it looks:
phi(x * y) = phi(x) * phi(y) * d / phi(d), where d = GCD(x, y)
It could get me somewhere but the problem is in d. I thought of accumamation of phi so my idea was if I know that N is equal to n1 * n2 * n3 *... * etc. then I can calculate phi(n1) and phi(n2) then get d = GCD(n1, n2) and phi(d) and calculate phi(n1 * n2). Next calcucate phi(n3) and do the same thing: phi(n1 * n2 * n3) = phi(n1 * n2) * phi(n3) * d / phi(d) where d = GCD(n1 * n2, n3). Same for n4 and so on. But it means that I need to store the product of all of ni to calculate d on each step. It leads to overflow.
Then learned that GCD is multiplicative too. GCD(a1 * a2, b) = GCD(a1, b) * GCD(a2, b). I still need all of the numbers ni but I can store them in array. It much better.
All of it probably could work if not the one damn moment. I have C(n, k) not A(n, k). It means that I have this
C(n, k) = n! / (k! * (n - k)!)
or this
C(n, k) = (k * (k + 1) * (k + 2) * ... * (n - 1) * n) / (n - k)!
The problem is that I need to reduce the numerator and denominator and without multiplycation of them, because I need to calculate phi separately to save as much time as I can. I tried to just cancel them separately. For example, if array[i] % k == 0, so now array[i] = array[i] / k but it doesn't work because sometimes I've got numbers in the denominator that couldn't canceled by one specific number in the numerator. For example I had a case when I had 4 in denominator but in numerator I only had many 2. Other way of calceling of denominator is factorization, but it takes all the time that I saved before. I prefere to avoid factorization.
That's where I stack. If you have any ideas, I gladly learn them.
Thanks in advance, sorry for poor english)
To calculate phi(C(n, k) mod 1000000007),...
Since 1000000007 is prime, you're in luck.
Since for 0 <= k <= n < 500000 n,k and n-k are all strictly less than prime p = 1000000007 then p cannot divide any of their factorials. Therefore,
C(n, k) = n! / (k! * (n - k)!) mod 1000000007
= (n! mod 1000000007) / (((k! mod 1000000007) * ((n - k)! mod 1000000007)) mod 1000000007
You can calculate the multiplicative inverses of non-zero residues mod 1000000007 using the Extended Euclidean Algorithm, or in this case since 1000000007 is prime, take the 1000000005th modular power. You also don't need big number libraries, 64 bit will manage this if you take the modular value after each multiplication. You can then easily factorize the result to get the Euler Totient.
To calculate phi(C(n, k)) mod 1000000007,...
First thing to notice is that all prime factors of C(n, k) must be less than or equal to n which in your example, for n < 500000 is quite a managable number for trial division but you should be able to solve this without having to manage such really huge numbers as C(n, k).
You need to find out how many times, m, prime p divides C(n, k) for each prime <= n.
m = (no. of times p divides n!) - (no. of times p divides k!) - (no. of times p divides (n-k)!)
where
no. of times p divides n! = floor(n/p) + floor(n/(p^2)) + floor(n/(p^3)) + ...
etc.. Then you have the prime factorization of C(n, k). Calculating the Euler Totient phi is then simple
phi(C(n, k)) = prod_{p = 2 to pmax and m >= 1} phi(p^m)
where of course phi(p^m) = p^(m-1)(p-1). You can calculate the end result using only 64 bit arithmetic if you take the modular value after each multiplication with
phi(C(n, k)) mod 1000000007 = prod_{p = 2 to pmax (with m >= 1)} (phi(p^m) mod 1000000007) mod 1000000007