描述

这是一篇面对初级coder的题解。
知识点：数学 快速幂 等比数列 费马小定理
难度：三星

题解

题目：
定义函数 ，然后在给定a和b的情况下，求f(x)%10000000033的值。
分析：

首先需要用等比数列的求和公式对
计算乘方可采用
中的快速幂算法

方法一：直接计算

之前的乘方算法化简到最简单依旧需要计算两个大数乘法
long long 是8字节 两个long long相乘就到了是16字节，同时由于由于取模运算的模太大，所以必须对乘法进行处理，否则乘法溢出！

类比竖式乘法：设计如下乘法逻辑，对每步乘法运算取模 保证乘法不溢出： 
class Solution {
    const long long mod=10000000033LL;//取余常数
public:
    long long power(long long base, long long exponent) {
        if(exponent==0)
            return 1;
        long long answer = 1;
        while(exponent){
            if(exponent&1)        //如果n的当前末位为1
                answer =multi(answer,base);  //ans乘上当前的a
            base =multi(base,base);        //a自乘
            exponent >>= 1;       //n往右移一位
        }
        return answer;
    }
    long long multi(long long a, long long b) {//防止越界 乘法 每次只乘2字节
        long long ans =0;
        while(b){
            ans=(ans+a*(b&0xFFFFLL))%mod;//相乘累加
            b>>=16;//乘数右移2字节
            a=(a<<16)%mod;//被乘数左移2字节
        }
        return ans;
    }

    long long solve(int a, int b, int n) {
        if(n==0)
            return 0; //处理特殊情况
        long long ans=0;
        for(int i=a;i<=b;i++){
            ans+=power((long long)n,(long long)i) % mod;//按要求相加
            ans =ans % mod;
        }
        return ans;
    }
};
复杂度分析：
时间复杂度：快幂法的时间复杂度都是，同时由于没有做优化，总共需要进行次幂运算，所以时间复杂度为 
此处 
空间复杂度 ，由于没有使用额外的空间 空间复杂度为 
运行测试：
运行超时
运行时间1001ms 占用内存404KB

方法二：等比数列求和公式+费马小定理

考虑等比数列求和公式

但是其中的除法  难以取模 所以这里需要用到费马小定理求逆元
在这样的基础上，推导


根据等比数列公式有

根据上面的费马小定理有
即：
代入上式得
程序中记：

则所求 

class Solution {
    const long long mod=10000000033LL;//取余常数
public:
    long long power(long long base, long long exponent) {
        if(exponent==0)
            return 1;
        long long answer = 1;
        while(exponent){
            if(exponent&1)        //如果n的当前末位为1
                answer =multi(answer,base);  //ans乘上当前的a
            base =multi(base,base);        //a自乘
            exponent >>= 1;       //n往右移一位
        }
        return answer;
    }
    long long multi(long long a, long long b) {//防止越界 乘法 每次只乘2字节
        long long ans =0;
        while(b){
            ans=(ans+a*(b&0xFFFFLL))%mod;//相乘累加
            b>>=16;//乘数右移2字节
            a=(a<<16)%mod;//被乘数左移2字节
        }
        return ans;
    }
    long long solve(int a, int b, int n) {
        if(n==0)
            return 0; //处理特殊情况
        if(n == 1)//用费马小定理那步要求n！=1
            return b - a + 1;//直接返回n=1值
        long long a1=power((long long)n,(long long)a);
        long long anq=power((long long)n,(long long)(b+1));
        long long np=power((long long)n-1,(long long)(mod-2));
        return multi(anq-a1+mod,np);
        // write code here
    }
};
复杂度分析：
时间复杂度：快幂法的时间复杂度都是，同时由于采用费马小定理和等比数列求和公式做了优化，总共需要进行3次幂运算，

 
空间复杂度：由于没有使用额外的空间 空间复杂度为 
运行测试：
运行时间： 3 ms 占用内存：400K

总结

数学知识很重要