牛牛的函数 解题报告

给定，那么可以根据等比数列求和得到:
那么如果求 ，我们可以将等比数列求和之后的f(x)拆开计算，即求：
其中 即求关于 M 的逆元。
所以就转化为求两个个快速幂，然后在求一个逆元即可。但是有一个trick，就是M的范围是long long 的，所以在求快速幂的过程要加上一个快速乘法，因为两个long long相乘超过long long的值了。
时间复杂度：O((logn)^2)
空间复杂度：O(1)
代码如下：

typedef long long LL;
const LL MOD = 10000000033;
LL Multi(LL a, LL b){
    LL ans = 0;
    while(b){
        if(b & 1) ans = (ans + a) % MOD;
        b>>=1;
        a = (a + a) % MOD;
    }
    return ans;
}
LL Pow(LL a, LL b){
    LL ans = 1;
    while(b){
        if(b & 1) ans = Multi(ans, a);
        b>>=1;
        a = Multi(a, a);
    }
    return ans;
}
void Exgcd(LL a, LL b, LL &x, LL &y){
    if(b == 0){
        x = 1;
        y = 0;
        return;
    }
    LL x1, y1;
    Exgcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - (a/b)*y1;
}
class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return long长整型
     */
    long long solve(int a, int b, int n) {
        // write code here
        if(n == 0) return 0;
        if(n == 1) return b-a+1;
        LL ans = Pow(n, a);
        LL x, y;
        Exgcd(n-1, MOD, x, y);
        x = (x%MOD+MOD)%MOD;
        ans = Multi(ans, x);
        ans = Multi(ans, (Pow(n, b-a+1)-1));
        ans = (ans%MOD+MOD)%MOD;
        return ans;
    }
};