算法模板(六)基础数论

gcd与lcm

#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int x,int y){
    return x*y/gcd(x,y);
}
int a,b;
int main(){
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
    cout<<lcm(x,y);
    return 0;
}

Lucas求组合数

#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
int E[maxn];
void init(){
    E[0]=1;
    for(register int i=0;i<maxn;i++)E[i]=E[i-1]*i;
}
int inv(int a,int m){
    if(a==1)return a;
    return inv(m%a,m)*(m-m/a)%m;
}
int n,m;
int lucas(int n,int m,int p){
    int res=1;
    while(n&&m){
        int a=n%p;
        int b=m%p;
        if(a<b)return 0;
        res=res*E[a]%p*inv(E[a-b]*E[b]%p,p)%p;
        n/=p;
        m/=p;
    }
    return res;
}
int main(){
    init();
    cin>>n>>m;
    cout<<lucas(n,m,10000007);
    return 0;
}