一颗苹果

题目

经过了漫长的等候，是梦想我还是一个我。

小J和小R发现商业街新开了许多商店，他们趁着下课去逛了逛，他们发现其中有一家水果店看起来还不错（没给赞助就不说是哪家了）。

小R："你看这价格是正常人能买得起的吗。"

小J："这里的我们可能买不起，但是你看外面有颗苹果树，这上面的我们总能摘吧。"

小R："那你可以先数数这棵树上一共有多少颗苹果吗？"

江安校区有棵奇怪的苹果树，这棵树共有n+1层，标号为0~n。这棵树第0层只有一个节点，为根节点。已知这棵树为b叉树，且保证是一颗满b叉树。

现在，该树第n层的每个节点上都结出了一个苹果，小J和小R想知道共结了多少苹果。由于数量可能很大，答案要求输出mod k后的结果。

输入：给出第1层的节点数 b 和层数 n 和 k。
输出：输出苹果数mod k后的结果。

样例1：

3 2 10

9

样例2：

2 10 9

7

提示：对于 30% 的数据，保证 b≤100, n≤10, k≤100。对于 100% 的数据，保证 b<2³¹, n<2³¹, k≤2¹⁵。

思路

第n层节点数就是 bⁿ（满b叉树每层扩大b倍）。b 和 n 最大接近 2³¹，暴力连乘 O(n) 会超时。用快速幂：把指数不断折半，若当前位为1就乘进答案，每轮底数自乘，O(log n) 搞定。注意底数和中间结果都要及时对 mod 取余防溢出，同时 ans 初始化为 1%mod 处理 mod=1 的边界。

#include<bits/stdc++.h>
using namespace std;

// 快速幂
int qpow(long long b, long long n, long long mod) {
    b%=mod;
    long long ans=1%mod;
    while (n) {
        if (n & 1) {
            ans = ans * b % mod;
        }
        n >>= 1;
        b = b * b % mod;
    }
    return ans;
}

int main() {
    long long b,n,k;
    cin>>b>>n>>k;
    cout<<qpow(b,n,k);
    return 0;
}

复杂度分析

• 时间复杂度：O(log n)，指数每轮折半
• 空间复杂度：O(1)

← 返回菜鸟的coding