CPC23-4 K.喵喵的神·数

题意：给出整数T,P，求c(T,P) mod P。

解法：用卢卡斯定理。

卢卡斯定理：解决c(n,m) mod p问题。Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)。

本题m=p，所以Lucas(n,p,p)化简得(n/p)%p。

卢卡斯定理的证明在网上找了好多都看不懂···以后有机会再学吧。

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

using namespace std;

int main()

{

    int n;

    cin>>n;

    while(n--)

    {

        int t,p;

        cin>>t>>p;

        cout<<(t/p)%p<<endl;

    }

    return 0;

}

巴特西

CPC23-4 K.喵喵的神·数

最新文章

热门文章