题解 | #牛牛的函数#

题目：
求 ,在给定a和b的情况下求f(x)%10000000033的值。
方法一：暴力解法

直接暴力解***超时，而且直接乘法也会超出long long的限制

class Solution {
public:
    /**
     *
     * @param a int整型
     * @param b int整型
     * @param n int整型
     * @return long长整型
     */
    long long mod=10000000033;
    long long solve(int a, int b, int n) {
        // write code here
        long long res=0;
        for(int i=a;i<=b;i++){
            res=(res+power(n,i))%mod;
        }
        return res;
    }
    long long power(long long base,long long m){
        long long res=1;
        for(int i=0;i<m;i++){
            res=res*base%mod;
        }
        return res;
    }
};

复杂度：
时间复杂度：操作次数为 ,因此时间复杂度为

空间复杂度：,额外变量空间复杂度为常数级

方法二：等比数列求和+快速幂+快速乘+费马定理求逆元

• 等比数列求和：
• 快速幂算法可以提高效率，快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。如果指数是奇数时，我们抽出了一个底数的一次方，假如计算，这个我们先单独移出来,剩下的,又能够在执行“缩指数”操作了，把指数缩小一半，底数执行平方操作 ,把指数缩小一半，底数执行平方操作
  此时，指数又变成了一个奇数1，按照上面对指数为奇数的操作方法，再抽出一个底数的一次方，这里即为，这个单独移出来，但是此时指数却变成了0，也就意味着我们无法再进行“缩指数”操作了。
  

最后的结果是9*6561，指数为奇数5时，此时底数为9。当指数为奇数1时，此时的底数为6561。因此最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。

• 快速乘算法：快速幂算法中的和 如果两个数直接乘再取模可能会超出long long 限制，乘法其实就是把很多个加法运算合到一起。现在我们的乘***爆范围，那我们就把它转化为加法。但是我们不可能一个一个的加，这样复杂度会是 O(n) 级别，所以我们模仿2进制加法操作来完成。
  比如计算,11的二进制是1011,
  则
• 逆元： % *%,一个分数对一个整数取模时不能直接进行模运算，但可以进行乘法运算，则需要用到逆元，可以用费马小定理计算单个逆元，费马小定理：对于整数a与质数p，a与p互质则,1%,这里的mod=10000000033为质数，则%=1% * % %

class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return long长整型
     */
    long long mod=10000000033;
    long long solve(int a, int b, int n) {
        // write code here
        if(n==0)return 0;
        if(n==1)return b-a+1;
        long long res=(fastpower(n,b+1)-fastpower(n,a)+mod)%mod;
        long long temp=fastpower(n-1,mod-2);//费马定理和快速幂求逆元
        return ksc(res,temp);
    }
    //快速乘防止long long溢出
    long long ksc(long long x,long long y ){
        long long res=0;//加法初始化
        while(y){
            if(y&1)res=(res+x)%mod;//模仿二进制,最低位为1时累加
            x=(x<<1)%mod; y>>=1;//将x不断乘2达到二进制
        }return res;
    }
    long long fastpower(long long base,long long power){
        long long res=1;
        while(power>0){
            if((power&1)==1){
                res=ksc(res,base)%mod;
            }
            power>>=1;
            base=ksc(base,base)%mod;
        }
        return res;
    }
};

复杂度：
时间复杂度：快速乘和快速幂算法的时间复杂度都为 ,又因为快速幂和快速乘嵌套使用则总的算法时间复杂度为 ,
空间复杂度：,额外变量为常数级