两个整数的 N 和 K ，无论是在范围内的 100000 给出。

Two integers n and k, both ranging in 100000 is given.

我们如何计算LCM对于 N * N-1 C 0 （N的乘法和（N-1选0） ）， N * N-1 C 1 （N的乘法和（N-1选1））， N * < SUP> N-1 C 2 （N的乘法和（N-1选2）），.......... N * N-1 C K （N的乘法和（N-1选择K））的模 1000000007 。

How do we calculate the LCM for n*n-1C0(multiplication of n and (n-1 choose 0)), n*n-1C1(multiplication of n and (n-1 choose 1)), n*n-1C2(multiplication of n and (n-1 choose 2)), .........., n*n-1Ck(multiplication of n and (n-1 choose k)) in modulo 1000000007.

我只是找到所有的值，然后计算其中有很多问题模时的数字成长。

I am simply finding all values and then calculating the modulo which have lot of problems when the numbers grows up.

如何高效计算的呢？

推荐答案

一些想法：

可以很容易地看到，LCM（NX，NY）= N * LCM（X，Y） 因此，实际上这个问题降低到计算LCM对C系数。

It's easy to see that lcm(nx, ny) = n*lcm(x, y) So actually the problem reduced to calculating lcm for C coefficients.

还有一点很容易看出，LCM（X / A，X / B）= X / GCD（A，B），其中，GCD是一个最大公约数。

Also it is easy to see that lcm(x/a, x/b) = x/gcd(a, b), where gcd is a greatest common divisor.

如果你还记得是n选择k = N！/ K！（N-K）！这两个步骤减少了问题的计算

If you remember that n choose k = n!/k!(n-k)! these two steps reduces the problem to calculation of

最大公约数（0 N！！，1！第（n-1）！2！（N-2）！，...，K！（NK）！）

gcd(0!n!, 1!(n-1)!, 2!(n-2)!, ..., k!(n-k)!)

和然后除以N * N！由该值

and then dividing n*n! by this value.

最大公约数可以容易地通过计算欧几里德算法的。实际上有更简单的方法：

gcd can be easily computed by Euclidean algorithm. There's actually even easier approach:

GCD（我！（NI）！（我+ 1）！（NI-1）！）= I！（NI-1）！GCD（NI，I + 1）

gcd(i!(n-i)!, (i+1)!(n-i-1)!) = i!(n-i-1)!gcd(n-i, i+1)

（最后GCD，你仍然需要使用欧几里德算法。但现在很容易）。

(for the last gcd you still have to use Euclidean algorithm. but now it is easier).

实际上，你可以做所有的计算在环模1000000007.这意味着你可以在每个乘/除后采取的1000000007余，也不会影响到答案。

You can actually do all of the computations in a ring modulo 1000000007. It means that you can take a remainder of 1000000007 after each multiplication/addition, it wouldn't affect the answer.

在最后，你有两个值：

X = N * N！ MOD 1000000007

x = n*n! mod 1000000007

Y =最大公约数（0 N！！，1！第（n-1）！2！（N-2）！，...，K！（NK）！）模1000000007

y = gcd(0!n!, 1!(n-1)!, 2!(n-2)!, ..., k!(n-k)!) mod 1000000007

，你可以为z用x，这样

Instead of dividing these numbers, you can multiply x by z, such that

Z * Y = 1模1000000007

z*y = 1 modulo 1000000007

您可以阅读更多关于为什么这个作品在这篇文章，以及如何找到这样ž< A HREF =htt​​ps://en.wikipedia.org/wiki/Modular_multiplicative_inverse相对=nofollow>这里。

You can read more about why this works in this article and how to find such z here.