描述

这是一篇面对初级coder的题解。
知识点： 数学 快速幂 大数乘法 逆元（费马小定理）
难度： 三星

---

题解

题目：

分析：
同上一题有相似之处 区别在于对数据长度的要求更高，输入已经变成了字符串

最近越来越多的协议会定义16字节长的整型，gcc 在 4.6 以上版本就可以使用 __int128_t & __uint128_t 了。

但需要注意的是，_uint128_t & __int128_t 仅对64位程序才有定义，因此如果编译选项中加入了 -m32，会出现找不到定义的编译错误。

另外 _uint128_t & __int128_t 并非c/c++ 标准，所以gcc目前只支持基本运算符的操作，输入输出这些都需要另外实现。

方法一：暴力求解

long long 是8字节 两个long long相乘就到了是16字节，所以必须对乘法进行处理

class Solution {
    const __int128_t mod=10000000033LL;//取余常数
public:
    __int128_t power(__int128_t base, __int128_t exponent) {
        if(exponent==0)
            return 1;
        __int128_t answer = 1;
        while(exponent){
            if(exponent&1)        //如果n的当前末位为1
                answer =muti(answer,base);  //ans乘上当前的a
            base =muti(base,base);        //a自乘
            exponent >>= 1;       //n往右移一位
        }
        return answer;
    }
    __int128_t muti(__int128_t a, __int128_t b) {//防止越界 乘法 每次只乘2字节
        __int128_t ans =0;
        while(b){
            ans=(ans+a*(b&0xFFFFLL))%mod;//相乘累加
            b>>=16;//乘数右移2字节
            a=(a<<16)%mod;//被乘数左移2字节
        }
        return ans;
    }
    __int128_t s2int128(string s) {
        __int128_t ans = 0, digit = 1;
        for(int i=s.size()-1;i>=0;digit*=10,i--) {
            ans += digit * (s[i]-'0');
        }
        return ans;
    }
    long long solve(string sa, string sb, int n) {
        if(n==0)
            return 0; //处理特殊情况
        __int128_t a=s2int128(sa);
        __int128_t b=s2int128(sb);
        __int128_t ans=0;
        for(int i=a;i<=b;i++){
            ans+=muti(n,power((__int128_t)n,(__int128_t)i));//按要求相加
            ans =ans % mod;
        }
        return (long long) ans;
    }
};

运行测试：
运行时间 1001ms 占用内存 312KB
计算超时

方法二：数列求和+费马小定理逆元

class Solution {
    const __int128_t mod=10000000033LL;//取余常数
public:
    __int128_t power(__int128_t base, __int128_t exponent) {
        if(exponent==0)
            return 1;
        __int128_t answer = 1;
        while(exponent){
            if(exponent&1)        //如果n的当前末位为1
                answer =muti(answer,base);  //ans乘上当前的a
            base =muti(base,base);        //a自乘
            exponent >>= 1;       //n往右移一位
        }
        return answer;
    }
    __int128_t muti(__int128_t a, __int128_t b) {//防止越界 乘法 每次只乘2字节
        __int128_t ans =0;
        while(b){
            ans=(ans+a*(b&0xFFFFLL))%mod;//相乘累加
            b>>=16;//乘数右移2字节
            a=(a<<16)%mod;//被乘数左移2字节
        }
        return ans;
    }
    __int128_t s2int128(string s) {//字符串转int128
        __int128_t ans = 0, digit = 1;
        for(int i=s.size()-1;i>=0;digit*=10,i--) {
            ans += digit * (s[i]-'0');
        }
        return ans;
    }
    long long solve(string sa, string sb, int n) {
        if(n==0)
            return 0; //处理特殊情况
        __int128_t a=s2int128(sa);
        __int128_t b=s2int128(sb);
        __int128_t ans=0;
        if(n==1)//特殊情况
            return muti(muti(a+1+b,b-a),power(2,mod-2));
        __int128_t xa = muti(a+1-muti(a,n)+mod,power(n, a));//xa=(a+1-ax)*x^a
        __int128_t xb = muti(b+1-muti(b,n)+mod,power(n, b));//xb=(b+1-bx)*x^b
        return muti((xa - xb + mod), power(n - 1, mod - 3));//
    }
};

总结