本文共 1177 字，大约阅读时间需要 3 分钟。

题目链接:

题目描述

给定n组询问，每组询问给定三个整数a,b,p，其中p是质数，请你输出的值。

输入格式

第一行包含整数n。

接下来n行，每行包含一组a,b,p。

输出格式

共n行，每行输出一个询问的解。

数据范围

1≤n≤20,

1≤b≤a≤10^18,

1≤p≤10^5,

输入样例

3

5 3 7

3 1 5

6 4 13

输出样例

3

3

2

解题思路

题意:求的值。

• 100000组, 1 <= b <= a <= 2000, 递推 -> O(N^2).
• 10000组, 1 <= b <= a <= 10^5, 预处理 -> O(NlogN).
• 20组, 1 <= b <= a <= 10^18, p <= 10^5, 卢卡斯定理(lucas)
  

Accepted Code:

/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using namespace std;typedef long long ll;int Fast_Power(int a, int b, int p) {    int res = 1;    while (b) {        if (b & 1)            res = 1ll * res * a % p;        a = 1ll * a * a % p;        b >>= 1;    }    return res;}int Com_Num(int a, int b, int p) {    int res = 1;    for (int i = 1, j = a; i <= b; i++, j--)        res = 1ll * res * j % p * Fast_Power(i, p - 2, p) % p;    return res;}int lucas(ll a, ll b, int p) {    if (a < p && b < p)        return Com_Num(a, b, p);    return 1ll * Com_Num(a % p, b % p, p) * lucas(a / p, b / p, p) % p;}int main() {    int t;    scanf("%d", &t);    while (t--) {        int p;        ll a, b;        scanf("%lld%lld%d", &a, &b, &p);        printf("%d\n", lucas(a, b, p));    }    return 0;}
   

转载地址：http://rubtf.baihongyu.com/