题意分析

  • 定义函数 ，然后在给定a和b的情况下，求的值。 简单明了。

思路分析

  • 我们就按照题目的要求直接进行计算。但是我们发现这个题目我们在求幂次方的时候数字过大。而且很可能会爆。这里我们就要介绍快速幂的写法。快速幂就是让我们在对数的时间范围内快速计算幂次方的。这个思想有点类似于分治然后再进行归并的算法。

图片说明

  • 就比如上面的图，我们想要计算大的就先要计算小部分的，然后小部分的幂次方计算出来后就可以反过来推导出大的了。这一部分结合递归或者迭代就可以做到了。

  • 快速幂的代码如下

ll qp(ll a,ll b){
     ll c=1;
     while(b){
        if(b&1) c=c*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return c;
}

  • 我们观察上面的代码，我们发现，在这个过程中我们出现了乘法，但是我们发现这个mod数还是挺大的。也就是可能会存在两个数字相乘爆long long的情况。所以为了避免这种情况，这里我们还需要介绍一直用快速乘的写法，其实和快速幂的思想是类似的。我们把其中一个因数看作一个二进制，所以我们就相当于一个数字与一个二进制的数字进行一个乘法。这样是不会爆的。

  • 快速乘的写法如下

ll qc(ll a,ll b){
    ll c=0;
    while(b){
        if(b&1) c=(c+a)%mod;
        b>>=1;
        a=(a+a)%mod;
    }   
    retrun c;
}

  • 我们可以观察到这两种写法是十分类似的。那么现在我们是否就可以解决这个题目了呢？我们发现，a和b的范围实在是太大了，所以我们如果直接暴力枚举的话很有可能会TLE。怎么办？我们继续观察，我们发现，这个序列其实就是一个等比数列的前n项和的一部分，我们可以把这个函数拆分成两个等比数列的差。我们令g(n)表示0-n的，公比为q的前n项的和。那么这个题目就可以表示为。我们直到等比序列的前n项和为,那么直接套进去就行了。但是我们发现这里有一个分母，而且这个模数是一个素数，所以我们可以直接使用费马小定理来求逆元。

  • 这里大致分析一下逆元的求法。我们都知道，对于一个,如果m不能被a整除，那么这个就只能用分数进行表示吗？显然是否定的。那么我们可以使用费马小定理进行求解。让他表示为一个整数的形式。但是用费马小定理的前提是我们这个模数必须是一个素数。费马小定理就是。这样，我们就可以对本题进行求解了。

解法一 迭代版本

  • 代码如下
    • 快速幂和快速乘的时间复杂度都是级别的。然后总的时间复杂度就是
    • 只开了少数几个变量来求。空间复杂度为 
class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return long长整型
     */
    typedef  long long ll;
    const ll mod = 10000000033;
    // 快速幂的写法，计算a^b%mod的值
    ll qp(ll a,ll b){
        ll c=1;
        while(b>0){
            if(b&1) c=qc(a,c)%mod;
            b>>=1;
            a=qc(a,a)%mod;
        }
        return c;
    }
    // 快速乘的写法，计算a*b%mod的值
    ll qc(ll a,ll b){
        ll ans=0;
        while(b){
            if(b&1){
                ans=(ans+a)%mod;
            }
            b>>=1;
            a=(a+a)%mod;
        }
        return ans;
    }
    long long solve(int a, int b, int n) {
        // write code here
        if(n==0){
            return 0;
        }else if(n==1){
            return b-a+1;
        }else{
            // 利用等比数列的前n项和的计算公式
            ll up=(qp(n,b+1)-qp(n,a)+mod)%mod;
            // 逆元操作
            ll down=qp((ll)n-1,mod-2);
            down=(down%mod+mod)%mod;
            return (qc(up,down)+mod)%mod;
        }
    }
};

解法二 递归版本

  • 代码如下
    • 快速幂和快速乘的时间复杂度都是log级别的。然后总的时间复杂度就是
    • 只开了少数几个变量来求。空间复杂度为 
class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return long长整型
     */
    typedef long long ll;
    const ll mod=10000000033;
    // 快速幂的写法，计算a^b%mod的值
    ll qp(ll a,ll b){
        if(b==0) return 1;
        if(b&1) return qc(a,qp(a,b-1))%mod;
        else{
            ll mul=qp(a,b/2);
            return qc(mul,mul)%mod;
        }
    }
    // 快速乘的写法，计算a*b%mod的值
    ll  qc(ll a,ll b){
        if(b==0) return 0;
        if(b&1) return (a+qc(a,b-1))%mod;
        else{
            ll tmp=qc(a,b/2);
            return (tmp+tmp)%mod;
        }
    }
    long long solve(int a, int b, int n) {
        // write code here
        if(n==0){
            return 0;
        }else if(n==1){
            return b-a+1;
        }
         // 利用等比数列的前n项和的计算公式
        ll up=(qp(n,b+1)-qp(n,a)+mod)%mod;
        // 逆元操作
        ll down=qp((ll)n-1,mod-2);
        down=(down%mod+mod)%mod;
        return (qc(up,down)+mod)%mod;
    }
};