题目链接:https://www.acwing.com/problem/content/description/889/
时/空限制：1s / 64MB

题目描述

给定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 <bits/stdc++.h>
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;
}