如何我们计算ň取K模量的素数没有溢出

如何我们计算ň取K模量的素数没有溢出

本文介绍了如何我们计算ň取K模量的素数没有溢出?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

如何才能计算机(ñ取K )的C%M或C ++而不必调用溢出?

How can we computer (N choose K)% M in C or C++ without invoking overflow ?

有关的特殊情况下,当 N(4℃= N< = 1000) K(1< = K< = N) M = 1000000003

For the particular case when N (4<=N<=1000) and K (1<=K<=N) and M = 1000000003.

推荐答案

要计算(正选K)%M,可以分别计算出提名模数m,分母(K *(N - K )!)模数m,然后乘以提名的分母的模反元素(米)。由于M是素数,则可以使用费马小定理来计算乘法逆。

To compute (n choose k) % M, you can separately compute the nominator (n!) modulus M and the denominator (k!*(n - k)!) modulus M and then multiply the nominator by the denominator's modular multiplicative inverse (in M). Since M is prime, you can use Fermat's Little Theorem to calculate the multiplicative inverse.

有一个很好的解释,样本code,以下链接(问题SuperSum):

There is a nice explanation, with sample code, on the following link (problem SuperSum):

<一个href="http://www.top$c$cr.com/wiki/display/tc/SRM+467">http://www.top$c$cr.com/wiki/display/tc/SRM+467

这篇关于如何我们计算ň取K模量的素数没有溢出?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-13 17:28