蓝桥杯-数的潜能-求快速幂

题目

思路

--将数字拆分成加和的形式，并且相乘。数据范围到10的18次方，暴力肯定不行，要找规律。拆分成1肯定不行，对乘法没有贡献，2可以，3也可以，4、5、6等大于3的数字都可以用2和3来表示。所以就有了方向了，将数字拆分成2、3，其个数用num2和num3来表示，结果res就可以由幂运算求得。然后再进一步考虑，是拆成2好呢，还是拆成3好。先找几个例子看看，4可以拆成2 2和1 3，显然2 2更好，5可以拆成2 3，这个明显是最优情况，6可以拆成2 2 2和3 3，显然3 3更好，再往后看就和前面几种情况重复了。4 % 3 = 1, 5 % 3 = 2, 6 % 3 = 0，只有这3种情况了。所有的数对3取余余数只有0、1、2三种可能。如果余数为1，就将num3的个数-1，替换成2个2；如果余数为2，num2就等于1了；如果余数为0，那很好，全都是3，num3 = n / 3。

--下面最关键的就是求幂了，我刚开始用的pow()，幂指数太大了，不行，然后又用for循环，超时。最后在网上找了求快速幂的迭代方法。如果用for循环求幂，那就是3 * 3 * 3 * 3 * ...，但是如果用快速幂，就是先算3 * 3 = 9，指数x缩小2倍，然后9 * 9 = 81，指数x缩小再2倍，再接着81 * 81，x /= 2...类似于二分吧，如果x是奇数，再将底数乘以3就好了，采用的是一种降幂增低的方法。底数也在指数倍增长，减少了许多重复的计算。

--还有一点，就是n等于1的情况，我刚开始没有考虑到。

代码

#include <iostream>
#include <cmath>
using namespace std;

int mi(long long x){
    int y = 1; //初始化结果为1。 
    int ji = 3; //底数为3，也表示累乘的结果。 
    while (x){
        if (x & 1){ //and位运算，如果x二进制数的最低位为1，结果为1，否则是0。即x是奇数。 
            y = y * ji % 5218; 
        }
        ji = ji * ji % 5218;
        x /= 2; 
    } //x最后一定为1，再最后才为0。 
    
    return y;
} //迭代法快速求幂。 

int main(){
    long long n;
    cin >> n;
    
    if (n == 1){
        cout << "1" << endl;
        return 0;
    } //考虑n = 0的特殊情况。 
     
    long long num2, num3;
    num2 = num3 = 0;
    int yu = n % 3;
    if (yu == 0){
        num3 = n / 3;
    } //3*3 > 2*2*2 
    else if (yu == 1){
        num3 = n / 3 - 1;
        num2 = 2;
    } //1*3 < 2*2
    else{
        num3 = n / 3;
        num2 = 1;
    } //一个2，剩下的都是3 
    
    long long res = 1;
    for (int i = 0; i < num2; i++){
        res *= 2;
    }
    res = res * mi(num3) % 5218;
    cout << res << endl;
    
    return 0;
}