题解 | #牛牛的函数#

##思路： 题目的主要信息：

• 定义函数$f\left(x\right)=x^a+x^{a+1}+...+x^{b-1}+x^{b}f(x)\; =\; x^a\; +\; x^\{a+1\}\; +...+\; x^\{b-1\}\; +\; x^b$f(x)=xa+xa+1+...+xb−1+xb
• 已知$nn$n、$aa$a、$bb$b，求$f\left(n\right)\%10000000033f(n)\backslash \%10000000033$f(n)%10000000033

方法一：暴力解法（超时） 具体做法： 写一个循环算幂的函数，然后遍历$aa$a到$bb$b，将计算的幂结果相加并取模。

class Solution {
public:
    long long cal(int x, int i){ //计算x的i次幂
        long long res = 1;
        for(int j = 0; j < i; j++)
            res *= x;
        return res;
    }
    long long solve(int a, int b, int n) {
        long long res = 0;
        for(int i = a; i <= b; i++) //循环相加
            res = (res + cal(n, i)) % 10000000033;
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(b^2-a^2)O(b^2-a^2)$O(b2−a2)，内外循环加起来一共运算次数是$a+a+1+a+2+...+b-1+b=(a+b)\ast (b-a+1)/2a+a+1+a+2+...+b-1+b=(a+b)*(b-a+1)/2$a+a+1+a+2+...+b−1+b=(a+b)∗(b−a+1)/2
• 空间复杂度：$O\left(1\right)O(1)$O(1)，常数空间

方法二：数列求和+快速幂+快速乘法+逆元 具体做法： 这道题的数据很大，我们不仅要考虑超时的问题，还应该考虑爆long long的问题，因此我们需要多次优化：

• 对于相加运算次数，我们可以用数列求和解决
• 对于幂运算次数，我们可以用快速幂解决
• 对于爆long long的问题，我们可以用快速乘法，以及费马小定理的逆元解决

1. 数列求和。$f\left(x\right)=x^a+x^{a+1}+...+x^{b-1}+x^b=(x^{b+1}-x^a)/(x-1)f(x)\; =\; x^a\; +\; x^\{a+1\}\; +...+\; x^\{b-1\}\; +\; x^b=(x^\{b+1\}-x^a)/(x-1)$f(x)=xa+xa+1+...+xb−1+xb=(xb+1−xa)/(x−1)，这样一来我们就不用再循环相加了。

2. 快速幂。如果我们要计算$5^{10}5^\{10\}$510，常规的算法是$5\ast 5=255*5=25$5∗5=25，然后再$25\ast 5=12525*5=125$25∗5=125，如此往下，一共是$99$9次运算，即$n-1n-1$n−1次。但是我们可以考虑这样：$5\ast 5=255*5=25$5∗5=25(二次）、$25\ast 25=62525*25=625$25∗25=625（四次）、$625\ast 625=...625*625=...$625∗625=...（八次），这是一个二分的思维，运算次数缩减到了$lo{g}_{2}nlog\_2n$log2​n次，公式如下：

3. 快速乘法。直接计算$x^{a}x^a$xa会超出long long的表示范围，因此我们可以考虑用加法来代替乘法，并在这其中取模。就比如$a\ast b=a\ast (b_1+b_2+b_3+...)a*b=a*(b\_1+b\_2+b\_3+...)$a∗b=a∗(b1​+b2​+b3​+...)，其中$b_{i}b\_i$bi​是数字$bb$b的二进制各位，假设$a=5a=5$a=5，$b=110101b=110101$b=110101，我们有$a\ast b=a\ast (100000\ast 1+10000\ast 1+1000\ast 0+100\ast 1+10\ast 0+1\ast 1)a*b=a*(100000*1+10000*1+1000*0+100*1+10*0+1*1)$a∗b=a∗(100000∗1+10000∗1+1000∗0+100∗1+10∗0+1∗1)，如下表所示可以换成加法运算并在加法中取模：

4. 逆元。为了计算$(x^{b+1}-x^a)/(x-1)(x^\{b+1\}-x^a)/(x-1)$(xb+1−xa)/(x−1)我们也要超出long long限制的问题，因为有取模的关系。对此有一个数学定理（费马小定理）：如果$pp$p是一个质数，而整数$xx$x不是$pp$p的倍数，则有$x^{p-1}\%p\equiv 1x^\{p-1\}\; \backslash \%\; p\; \backslash equiv\; 1$xp−1%p≡1，我们取的模10000000033正是一个质数。上述公式两边同时除$xx$x得$x^{p-2}\%p\equiv 1/x\%px^\{p-2\}\; \backslash \%\; p\; \backslash equiv\; 1/x\; \backslash \%\; p$xp−2%p≡1/x%p，即$(x^{b+1}-x^a)/(x-1)\%mod\equiv (x^{b+1}-x^a)\%mod\ast 1/(x-1)\%mod(x^\{b+1\}-x^a)/(x-1)\; \backslash \%\; mod\; \backslash equiv\; (x^\{b+1\}-x^a)\; \backslash \%\; mod\; *\; 1/(x-1)\; \backslash \%\; mod$(xb+1−xa)/(x−1)%mod≡(xb+1−xa)%mod∗1/(x−1)%mod $\equiv (x^{b+1}-x^a)\%mod\ast (x-1{)}^{mod-2}\%mod\backslash equiv(x^\{b+1\}-x^a)\; \backslash \%\; mod\; *\; (x-1)^\{mod-2\}\; \backslash \%\; mod$≡(xb+1−xa)%mod∗(x−1)mod−2%mod

class Solution {
public:
    long long mod = 10000000033;
    long long fast(long long x, long long y){ //快速乘法
        long long res = 0;
        x %= mod;
        y %= mod;
        while(y){
            if(y & 1){
                res += x; //加法代替乘法，防止爆long long
                if(res >= mod)
                    res -= mod;
            }
            y = y >> 1;
            x = x << 1;
            if(x >= mod)
                x -= mod;
        }
        return res;
    }
    long long Pow(long long x, long long y){ //快速幂
        long long res = 1;
        while(y){
            if(y & 1) //可以再往上乘一个
                res = fast(res, x); 
            x = fast(x, x); //叠加
            y = y >> 1; //减少乘次数
        }
        return res;
    }
    long long solve(int a, int b, int n){
        if(n == 0)
            return 0;
        if(n == 1) 
            return b - a + 1;
        long long res = (Pow(n, b + 1) - Pow(n, a) + mod) % mod; //数列求和
        long long temp = Pow(n - 1, mod - 2); //费马小定理求逆元
        return fast(res, temp);
    }
};

复杂度分析：

• 时间复杂度：$O\left(\right(lo{g}_{2}n{)}^2)O((log\_2n)^2)$O((log2​n)2)，这里的$n=max(b+1,a,mod-2)n=max(b+1,a,mod-2)$n=max(b+1,a,mod−2)，不管是快速幂还是快速乘法都是$O\left(lo{g}_{2}n\right)O(log\_2n)$O(log2​n)，这里嵌套使用
• 空间复杂度：$O\left(1\right)O(1)$O(1)，常数空间