我知道奇怪的组合，但这是我的问题： 我们有 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 ).
我尝试了几次，但不幸的是我只能为n做出好东西<= 50000. I had a few approaches, but some of them I couldn't implement properly.
欧拉函数是相对质数的乘法，而且如果你得到N的所有质数就可以很容易地计算它。所以我尝试了C（n，k）的因式分解但失败了。我只知道 O(N^0.5) 的分解算法，所以花了太多时间。我阅读了其他因式分解算法，但它们的复杂度仅为 O(N^0.25)。我觉得还不够
然后我了解到即使对于 GCD > 1 的数字，欧拉函数也可以是乘法的，但它需要修正。这是它的样子：
phi(x * y) = phi(x) * phi(y) * d / phi(d)，其中 d = GCD(x, y)
它可以让我到达某个地方，但问题出在 d 中。我想到了 phi 的累积，所以我的想法是，如果我知道 N 等于 n1 * n2 * n3 *... * 等，那么我可以计算 phi(n1) 和 phi(n2) 然后得到 d = GCD(n1, n2) 和 phi(d) 并计算 phi(n1 * n2)。接下来计算 phi(n3) 并做同样的事情： phi(n1 * n2 * n3) = phi(n1 * n2) * phi(n3) * d / phi(d) 其中 d = GCD(n1 * n2, n3) . n4 等也一样。但这意味着我需要存储所有ni的乘积来计算每一步的d。它导致溢出。
然后才知道GCD也是乘法的。 GCD(a1 * a2, b) = GCD(a1, b) * GCD(a2, b)。我仍然需要所有数字 ni 但我可以将它们存储在数组中。它好多了。
如果不是那该死的一刻，所有这些都可能会奏效。我有 C(n, k) 而不是 A(n, k)。这意味着我有这个
C(n, k) = n! / (k! * (n - k)!)
或者这个
C(n, k) = (k * (k + 1) * (k + 2) * ... * (n - 1) * n) / (n - k)!
问题是我需要减少分子和分母并且不乘它们，因为我需要单独计算 phi 以尽可能节省时间。我试着单独取消它们。例如，如果 array[i] % k == 0，那么现在 array[i] = array[i] / k 但它不起作用，因为有时我的分母中有数字不能被一个抵消分子中的特定数字。例如，我有一个案例，我的分母有 4，但分子只有很多 2。分母的另一种计算方法是因式分解，但它占用了我之前节省的所有时间。我宁愿避免因式分解。
那是我堆叠的地方。如果你有任何想法，我很乐意学习它们。
提前致谢，抱歉英语不好）