给定三个数字n、r和p，计算 N C R 这里p是一个大于n的素数 N C R 是 二项式系数 . 例子：
null
Input: n = 10, r = 2, p = 13Output: 6Explanation: 10C2 is 45 and 45 % 13 is 6.Input: n = 6, r = 2, p = 13Output: 2
我们在之前的帖子中讨论过以下方法。 计算 N C R %p |集1（介绍和动态规划解决方案） 计算 N C R %p |集2（卢卡斯定理） 本文讨论了基于费马定理的解。 背景： 费马小定理与模逆 费马的小定理表明，如果p是素数，那么对于任何整数a，这个数 A. P –a 是p的整数倍。在模运算的表示法中，这表示为： A. P =a（mod p） 例如，如果a=2，p=7，则为2 7. =128，128–2=7×18是7的整数倍。 如果a不可被p整除，则费马的小定理等价于该陈述 A. p-1 – 1 是p的整数倍，即 A. p-1 =1（模p） 如果我们用a乘以两边 -1 ，我们得到了。 A. p-2 =a -1 （国防部p） 所以我们可以找到 模逆 像 p-2 . 计算：
We know the formula for nCr nCr = fact(n) / (fact(r) x fact(n-r)) Here fact() means factorial. nCr % p = (fac[n]* modIverse(fac[r]) % p * modIverse(fac[n-r]) % p) % p;Here modIverse() means modular inverse undermodulo p.
下面是上述算法的实现。在下面的实现中，使用数组fac[]存储所有计算出的阶乘值。
C++
// A modular inverse based solution to // compute nCr % p #include <bits/stdc++.h> using namespace std; /* Iterative Function to calculate (x^y)%p in O(log y) */ unsigned long long power(unsigned long long x, int y, int p) { unsigned long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Returns n^(-1) mod p unsigned long long modInverse(unsigned long long n, int p) { return power(n, p - 2, p); } // Returns nCr % p using Fermat's little // theorem. unsigned long long nCrModPFermat(unsigned long long n, int r, int p) { // If n<r, then nCr should return 0 if (n < r) return 0; // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n-r unsigned long long fac[n + 1]; fac[0] = 1; for ( int i = 1; i <= n; i++) fac[i] = (fac[i - 1] * i) % p; return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; } // Driver program int main() { // p must be a prime greater than n. int n = 10, r = 2, p = 13; cout << "Value of nCr % p is " << nCrModPFermat(n, r, p); return 0; } |
JAVA
// A modular inverse based solution to // compute nCr % import java.io.*; class GFG { /* Iterative Function to calculate (x^y)%p in O(log y) */ static int power( int x, int y, int p) { // Initialize result int res = 1 ; // Update x if it is more than or // equal to p x = x % p; while (y > 0 ) { // If y is odd, multiply x // with result if (y % 2 == 1 ) res = (res * x) % p; // y must be even now y = y >> 1 ; // y = y/2 x = (x * x) % p; } return res; } // Returns n^(-1) mod p static int modInverse( int n, int p) { return power(n, p - 2 , p); } // Returns nCr % p using Fermat's // little theorem. static int nCrModPFermat( int n, int r, int p) { if (n<r) return 0 ; // Base case if (r == 0 ) return 1 ; // Fill factorial array so that we // can find all factorial of r, n // and n-r int [] fac = new int [n + 1 ]; fac[ 0 ] = 1 ; for ( int i = 1 ; i <= n; i++) fac[i] = fac[i - 1 ] * i % p; return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; } // Driver program public static void main(String[] args) { // p must be a prime greater than n. int n = 10 , r = 2 , p = 13 ; System.out.println( "Value of nCr % p is " + nCrModPFermat(n, r, p)); } } // This code is contributed by Anuj_67. |
Python3
# Python3 function to # calculate nCr % p def ncr(n, r, p): # initialize numerator # and denominator num = den = 1 for i in range (r): num = (num * (n - i)) % p den = (den * (i + 1 )) % p return (num * pow (den, p - 2 , p)) % p # p must be a prime # greater than n n, r, p = 10 , 11 , 13 print ( "Value of nCr % p is" , ncr(n, r, p)) |
C#
// A modular inverse based solution to // compute nCr % p using System; class GFG { /* Iterative Function to calculate (x^y)%p in O(log y) */ static int power( int x, int y, int p) { // Initialize result int res = 1; // Update x if it is more than or // equal to p x = x % p; while (y > 0) { // If y is odd, multiply x // with result if (y % 2 == 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Returns n^(-1) mod p static int modInverse( int n, int p) { return power(n, p - 2, p); } // Returns nCr % p using Fermat's // little theorem. static int nCrModPFermat( int n, int r, int p) { if (n<r) return 0; // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n-r int [] fac = new int [n + 1]; fac[0] = 1; for ( int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p; return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; } // Driver program static void Main() { // p must be a prime greater than n. int n = 10, r = 11, p = 13; Console.Write( "Value of nCr % p is " + nCrModPFermat(n, r, p)); } } // This code is contributed by Anuj_67 |
PHP
<?php // A modular inverse // based solution to // compute nCr % p // Iterative Function to // calculate (x^y)%p // in O(log y) function power( $x , $y , $p ) { // Initialize result $res = 1; // Update x if it // is more than or // equal to p $x = $x % $p ; while ( $y > 0) { // If y is odd, // multiply x // with result if ( $y & 1) $res = ( $res * $x ) % $p ; // y must be // even now // y = y/2 $y = $y >> 1; $x = ( $x * $x ) % $p ; } return $res ; } // Returns n^(-1) mod p function modInverse( $n , $p ) { return power( $n , $p - 2, $p ); } // Returns nCr % p using // Fermat's little // theorem. function nCrModPFermat( $n , $r , $p ) { if ( $n < $r ) return 0; // Base case if ( $r ==0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n-r //$fac[$n+1]; $fac [0] = 1; for ( $i = 1; $i <= $n ; $i ++) $fac [ $i ] = $fac [ $i - 1] * $i % $p ; return ( $fac [ $n ] * modInverse( $fac [ $r ], $p ) % $p * modInverse( $fac [ $n - $r ], $p ) % $p ) % $p ; } // Driver Code // p must be a prime // greater than n. $n = 10; $r = 2; $p = 13; echo "Value of nCr % p is " , nCrModPFermat( $n , $r , $p ); // This code is contributed by Ajit. ?> |
Javascript
<script> // A modular inverse based solution // to compute nCr % p /* Iterative Function to calculate (x^y)%p in O(log y) */ function power(x, y, p) { // Initialize result let res = 1; // Update x if it is more than or // equal to p x = x % p; while (y > 0) { // If y is odd, multiply x // with result if (y % 2 == 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Returns n^(-1) mod p function modInverse(n, p) { return power(n, p - 2, p); } // Returns nCr % p using Fermat's // little theorem. function nCrModPFermat(n, r, p) { if (n<r) { return 0; } // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n-r let fac = new Array(n + 1); fac[0] = 1; for (let i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p; return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; } // p must be a prime greater than n. let n = 10, r = 2, p = 13; document.write( "Value of nCr % p is " + nCrModPFermat(n, r, p)); </script> |
输出：
Value of nCr % p is 6
改进： 在竞争性编程中，我们可以预先计算给定上限的fac[]，这样我们就不必为每个测试用例计算它。我们还可以在任何地方使用无符号long-long-int来避免溢出。 本文由 尼希尔·帕皮塞蒂 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
