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;
}
