牛牛的函数

typedef long long ll;
class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return long长整型
     */
    const ll M = 10000000033;
    ll F(ll x, ll y){
        ll s = 0;
        x %= M;
        y %= M;
        while(y){
            if(y&1){
                s += x;
                if(s>=M)
                    s -= M;
            }
            y>>=1;
            x<<=1;
            if(x>=M)
                x -= M;
        }
        return s;
    }
    ll P(ll x, ll y){
        ll s = 1;
        while(y){
            if(y&1)
                s = F(s, x);
            x = F(x, x);
            y>>=1;
        }
        return s;
    }
    long long solve(int a, int b, int n) {
        if(n==0)
            return 0;
        if(n==1)
            return b-a+1;
        ll s = (P(n, b+1)-P(n, a)+M) % M;
        ll t = P(n-1, M-2);
        return F(s ,t);
    }
};

题意：求(n^a + n^(a + 1) +...+n^b ) % 10000000033的值。
数据范围：

0<=x,a,b<=1e9, 且 a<=b

前置知识： 同余

思路1：

由于题目数据范围巨大，故 不能使用常规幂运算 进行计算；需要使用快速幂进行加速计算，并且使用快速乘法来防止数据溢出，但是由于此方法需要遍历a ~ b，并且每次遍历有两次快速幂计算,时间复杂度为n（log（n * logn）），因此会超时。

思路2：
在思路1 的基础上，通过 等比数列求和公式 和求 逆元 进行优化。

#define LL long long
const LL mod = 10000000033;
class Solution
{
    public:
    //快速乘法
    LL quick_mul(LL a,LL b){
        a%=mod;
        b%=mod;
        LL res=0;
        while(b){
            if(b&1){
                res+=a;
                if(res>=mod)
                res-=mod;
            }
            b>>=1;
            a<<=1;
            if(a>=mod) a-=mod;
        }
        return res;
    }
    LL quick_pow(LL a, LL b){
        LL res = 1;
        while(b){
            if(b&1){
                res = quick_mul(res, a);
            }
            a = quick_mul(a, a);
            b >>= 1;
        }
        return res;
    }
    long long solve(int a,int b,int n){
        if(n==0) return 0;
        if(n==1) return b-a+1;
        LL res=(quick_pow(n, b + 1)- quick_pow(n, a)+ mod) % mod;
        //费马小定理求逆元
        LL inv=quick_pow(n - 1, mod - 2);
        return quick_mul(res,inv);
    }
};