本文主要是介绍CPC23三 K.（Lucas定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
K.喵喵的神·数
Time Limit: 1 Sec Memory Limit: 128 MB
Time Limit: 1 Sec Memory Limit: 128 MB
Description
喵喵对组合数比较感兴趣，并且对计算组合数非常在行。同时为了追求有后宫的素质的生活，喵喵每天都要研究质数。
我们先来复习一下什么叫做组合数。对于正整数P、T
然后我们再来复习一下什么叫质数。质数就是素数，如果说正整数N的约数只有1和它本身，N就是质数；另外，1不是质数。
今天，喵喵想要知道
Input
输入第一行是一个整数N（N<=1000）。
接下来N行，每行包括一个正整数T和一个质数P（1<=P<=T<231）。
Output
包括N行，根据输入的顺序，每一行为一个整数：
Sample Input
2
3 2
10 3
Sample Output
1
解题思路：
用lucas定理解决。Lucas定理是用来求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）。lucas定理如下：
Lucas(n,m,p)=c(n%p,m%p)* Lucas(n/p,m/p,p)
Lucas(x,0,p)=1;
在本题中m = p，所以c(n%p,m%p) = c(n%p,0) = 1 ，所以Lucas(n,m,p) = Lucas(n/p,m/p,p) = Lucas(n/p,1,p) = c(n/p , 1) mod p = （n / p）% p。
完整代码：
在本题中m = p，所以c(n%p,m%p) = c(n%p,0) = 1 ，所以Lucas(n,m,p) = Lucas(n/p,m/p,p) = Lucas(n/p,1,p) = c(n/p , 1) mod p = （n / p）% p。
完整代码：
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;/** Constant List .. **/ //{const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;int main()
{#ifdef DoubleQfreopen("in.txt","r",stdin);#endifint n;scanf("%d",&n);{while(n--){int t , p;while(~scanf("%d%d",&t,&p)){printf("%d\n" , (t / p) % p);}}}
}
这篇关于CPC23三 K.（Lucas定理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
