AHSOFNU NOIP模拟题-11 T1(快速幂)

满树的第$n$层(从$0$标号)的节点个数为$b^n$,这里$b, n$很大就要快速幂处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define FN2 "count"
using namespace std;
ll b, n, k;
ll poww(ll a, ll b) {
ll ret = 1, s = a;
while (b) {
if (b&1) ret = (ret * s) % k;
s = (s * s) % k;
b >>= 1;
}
return ret;
}
void clean() {}
void solve() {
clean();
printf("%I64d\n", poww(b, n));
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
scanf("%I64d%I64d%I64d", &b, &n, &k), solve();
fclose(stdin); fclose(stdout);
return 0;
}

果实计数
(count.pas/.c/.cpp)
时间限制:1s,空间限制32MB
题目描述:
淘淘家有棵奇怪的苹果树,这棵树共有n+1层,标号为0~n。这棵树第0层只有一个节点,为根节点。已知这棵树为b叉树,且保证是一颗满b叉树。如图为一颗满3叉树。
现在,该树第n层的每个节点上都结出了一个苹果,淘淘想知道共结了多少苹果。由于数量可能很大,答案要求输出mod k后的结果。
输入描述:
给出第1层的节点数b和层数n和k.
输出描述:
输出苹果数mod k后的结果。
样例输入:
2 10 9
样例输出:
7
数据范围:
30%的数据保证:b<=100,n<=10, k<=100.
100%的数据保证:b<2^31,n<2^31,k<=2^15.

------ 本文结束 ------