牛牛的函数2 解题报告

给定，我们对求一下积分，得到
将上述公式进行等比数列求和，那么此时我们在讲上述公式求导，然后变为：
当我们推导出如上公式之后，剩下的就很简单了，该求逆元的求逆元，该求快速幂的求快速幂。但是我们需要注意的以下几点：

1. 输入的数字很大，为字符串，所以我们在进行计算的时候需要注意。
2. 根据费马小定理，我们在计算指数取模的时候要对(MOD-1)取模而不是对MOD取模
3. 由于取模数较大，所以需要在快速幂的时候加上快速乘法。
   代码如下：

   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 sa string字符串 
     * @param sb string字符串 
     * @param n int整型 
     * @return long长整型
     */
    long long solve(string sa, string sb, LL n) {
        // write code here
        LL a1=0, b1=0, a2=0, b2=0; cin>>sa>>sb>>n;
        if(n == 0) return 0;
        for(int i=0; i<sa.length(); i++){
            a1 = a1*10+(sa[i]-'0');
            a1 %= (MOD-1);
            a2 = a2*10+(sa[i]-'0');
            a2 %= MOD;
        }
        for(int i=0; i<sb.length(); i++){
            b1 = b1*10+(sb[i]-'0');
            b1 %= (MOD-1);
            b2 = b2*10+(sb[i]-'0');
            b2 %= MOD;
        }
        LL x, y;
        if(n == 1){
            Exgcd(2, MOD, x, y);
            x = (x%MOD+MOD)%MOD;
            LL ans = Multi(a2+b2+1, b2-a2);
            ans = Multi(ans, x);
            ans = (ans%MOD+MOD)%MOD;
            return ans;
        }
        Exgcd(n-1, MOD, x, y);
        x = (x%MOD+MOD)%MOD;
        x = Multi(x, x);
        LL ans1 = Multi(b2,Pow(n, b1+1)) - Multi(b2+1, Pow(n, b1));
        LL ans2 = Multi(a2,Pow(n, a1+1)) - Multi(a2+1, Pow(n, a1));
        ans1 -= ans2;
        ans1 = (ans1%MOD+MOD)%MOD;
        ans1 = Multi(ans1, x);
        LL ans = (ans1%MOD+MOD)%MOD;
        return ans;
    }
   };