描述

本来想写写过程啊，想法啊，什么的。可是我太懒了。把用法写一下算了。
这个代码两个功能：

  1. n!=a*p^e，p是素数。求a%p 和 e（最大）
  2. 求组合数C n k,在n个数中选k个的组合数 模 p的答案。
  3. 这里p要小于“#define NV 1000005”

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
#define NV 1000005
/* 
复杂度(log n),表示a关于取摸n的逆元，
要求 a，n互质
*/
//扩展欧几里得算法
ll extend_gcd(ll a, ll b, ll &x, ll &y)//求解ax+by=gcd(a,b)
{
     if (b == 0) {
        x = 1, y = 0;
        return a;
     }
    else{
            ll r = extend_gcd(b, a % b, y, x); //递归求解
            y -= x * (a / b);
            return r;
    }//x=(x%b+b)%b x的最小整数解
}
//运用扩展欧几里得算法求
ll mod_inverse(ll a, ll n)
{
    ll x, y;
    extend_gcd(a, n, x, y);
    x = (x % n + n) % n;
    return x;
}
 
ll fact[NV],n,p,e,k;
ll mod_fact(ll n, ll p ,ll & e){
    e = 0;
    if(n == 0) return 1;
    ll res = mod_fact(n / p , p ,e);
    e += n / p;
    if(n / p % 2 != 0)return res * (p - fact[n % p]) % p;
    return res * fact[n % p] % p;
}
ll mod_comb(ll n , ll k , ll p){
    if(n < 0 || k < 0 || n < k )return 0;
    ll e1 ,e2 , e3;
    ll a1 = mod_fact(n ,p ,e1) , a2 = mod_fact(k , p , e2) , a3 = mod_fact( n-k , p ,e3 );
    if( e1 > e2 +e3 )return 0 ;
    return a1 * mod_inverse(a2 * a3 % p ,p) % p;
}
void init(){
    ll tmp=1;fact[0]=1;
    for(int i=1 ; i< p ; i++){
        tmp =tmp * i;
        fact[i] = tmp % p;
    }
}
int main(){
    cout<<"n!=a*p^e"<<endl;
    cout<<"p is a prime number , puts in n  , p (1-100005) ,in order"<<endl;
    cout<<"return a%p"<<endl;
    cin>>n>>p;
    init();
    for(int i=0 ; i<p ;i++)
        printf("%I64d%c",fact[i],i==p-1 ? '\n':' ');
    cout<<"a%p = "<<mod_fact(n,p,e)<<endl;
    cout<<"e = "<<e<<endl;puts("_______________________________________");
    cout<<"C n k  mod p  |n个数取k个的组合数 % p"<<endl;
    cout<<"p is a prime number gets n , k, p in order "<<endl;
    cin>>n>>k>>p;init();
    cout<<mod_comb(n,k,p)<<endl;
    return 0;
}