输入a,b,求Cba的值。
注意结果可能很大,需要使用高精度计算。
输入格式
共一行,包含两个整数a和b。
输出格式
共一行,输出Cba的值。
数据范围
1≤b≤a≤5000
输入样例:
5 3
输出样例:
10
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5210;
ll primes[N],cnt;
ll st[N],sum[N];
void gets_primes(ll n) //找0-a的质数
{
for(ll i=2;i<=n;i++)
{
if(!st[i])primes[cnt++]=i;
for(ll j=0;primes[j]<=n/i;j++)
{
st[i*primes[j]]=1;
if(i%primes[j]==0)break;
}
}
}
ll get(ll n,ll p) //找n!中p的数;
{
ll res=0;
while (n)
{
res+=n/p;
n/=p;
}
return res;
}
vector<ll> mul(vector<ll>A,ll b)
{
vector<ll>C;
ll t=0;
for(ll i=0;i<A.size()||t;i++)
{
if(i<A.size())t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
return C;
}
int main()
{
ll a,b;
cin>>a>>b;
gets_primes(a);
for(ll i=0;i<cnt;i++)
{
ll p=primes[i];
sum[i]=get(a,p)-get(b,p)-get(a-b,p);
}
vector<ll>res;
res.push_back(1); //初始化;
for(ll i=0;i<cnt;i++)
{
for(ll j=0;j<sum[i];j++)
{
res=mul(res,primes[i]);
}
}
for(ll i=res.size()-1;i>=0;i--)cout<<res[i]; //逆向输出;
cout<<endl;
}