伦斯定理——算法数论里面比较难的 - 黑马程序员技术交流社区

[size=1em][size=1em]#include<iostream>
[size=1em]#include<cstdio>
[size=1em]#include<cstring>
[size=1em]#include<cstdlib>
[size=1em]#include<set>
[size=1em]#include<vector>
[size=1em]#include<algorithm>
[size=1em]#define ll long long
[size=1em]using namespace std;
[size=1em]int n,m;
[size=1em]const int p=10007;
[size=1em]int qpow(int a,int b)
[size=1em]{
[size=1em] int ans;
[size=1em] for(ans=1;b;b>>=1,a=a*a%p)
[size=1em]       if(b&1)ans=ans*a%p;
[size=1em] return ans;
[size=1em]}
[size=1em]int getc(int n,int m)
[size=1em]{
[size=1em] if(n<m)return 0;
[size=1em] if(m>n-m)m=n-m;
[size=1em] ll s1=1,s2=1;
[size=1em] for(int i=0;i<m;i++)
[size=1em] {
[size=1em]       s1=s1*(n-i)%p;
[size=1em]       s2=s2*(i+1)%p;
[size=1em] }
[size=1em] return s1*qpow(s2,p-2)%p;
[size=1em]}
[size=1em]int lucas(int n,int m)
[size=1em]{
[size=1em] if(m==0)return 1;
[size=1em] return <a target="_blank" href="/subview/751658/751658.htm">getc</a>(n%p,m%p)*lucas(n/p,m/p)%p;
[size=1em]}
[size=1em]int main()
[size=1em]{
[size=1em] scanf("%d%d",&n,&m);
[size=1em] printf("%d\n",lucas(n,m));
[size=1em] return 0;
[size=1em]}