题解 | #牛牛的函数2#

题目：
求，然后在给定a和b的情况下，求f(x)%10000000033的值。
其中0<=n<=,1<=a <= b-1<=

方法一：暴力解法
为避免数据溢出，我们用__int128处理大数据，将字符串转化为 __int128类型，并使用迭代求幂，会出现超时

#define lint __int128//处理大数据
const lint mod=10000000033;
class Solution {
public:
    /**
     * 
     * @param sa string字符串 
     * @param sb string字符串 
     * @param n int整型 
     * @return long长整型
     */

    long long solve(string sa, string sb, int n) {
        // write code here
        if(n==0)return 0;
        lint a=stolint(sa),b=stolint(sb);
        lint res=0;
        for(lint i=a+1;i<=b;i++){
            res=(res+i*power(n,i-1))%mod;
        }
        return res;
    }
    //将字符串转化为lint类型
    lint stolint(string s){
        lint res=0,mask=1;
        for(int i=s.size()-1;i>=0;i--){
            res+=(s[i]-'0')*mask;
            mask*=10;
        }
        return res;
    }
    lint power(lint base,lint m){
        lint res=1;
        for(lint i=0;i<m;i++){
            res=res*base%mod;
        }
        return res;
    }
};

复杂度：
时间复杂度：循环次数：,因此时间复杂度为
空间复杂度：,额外变量空间复杂度为常数级

方法二：快速幂+快速乘+逆元

• 因为1<=a <= b-1<=，这里使用long long 还是会超出范围，因此我们使用__int128，stolint函数将字符串转为lint类型
• 错位相减法求f(x):
  1:
  2：
  1-2:
  则
• 快速幂算法可以提高效率，快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。如果指数是奇数时，我们抽出了一个底数的一次方，假如计算，这个我们先单独移出来,剩下的,又能够在执行“缩指数”操作了，把指数缩小一半，底数执行平方操作 ,把指数缩小一半，底数执行平方操作
  此时，指数又变成了一个奇数1，按照上面对指数为奇数的操作方法，再抽出一个底数的一次方，这里即为，这个单独移出来，但是此时指数却变成了0，也就意味着我们无法再进行“缩指数”操作了。
  

最后的结果是9*6561，指数为奇数5时，此时底数为9。当指数为奇数1时，此时的底数为6561。因此最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。

• 快速乘算法：如果两个数直接乘再取模可能会超出限制，乘法其实就是把很多个加法运算合到一起。现在我们的乘***爆范围，那我们就把它转化为加法。但是我们不可能一个一个的加，这样复杂度会是 O(n) 级别，所以我们模仿2进制加法操作来完成。
  比如计算,11的二进制是1011,
  则
• 逆元：%,一个分数对一个整数取模时不能直接进行模运算，但可以进行乘法运算，则需要用到逆元，可以用费马小定理计算单个逆元，费马小定理：对于整数a与质数p，a与p互质则,1%,这里的mod=10000000033为质数，则%=1% *%=%=%,当n=1时，,根据费马小定理得%=1% * %=%=%

#define lint __int128//处理大数据
const lint mod=10000000033;
class Solution {
public:
    /**
     *
     * @param sa string字符串
     * @param sb string字符串
     * @param n int整型
     * @return long长整型
     */

    long long solve(string sa, string sb, int n) {
        // write code here
        if(n==0)return 0;

        lint a=stolint(sa),b=stolint(sb);
        if(n==1)return ksc(ksc(a+1+b,b-a),fastpower(2, mod-2));
        lint temp1=(ksc(b,fastpower(n,b+1))-ksc(b+1,fastpower(n,b))+mod)%mod;
        lint temp2=(ksc(a,fastpower(n,a+1))-ksc(a+1,fastpower(n,a))+mod)%mod;
        lint temp3=fastpower(n-1,mod-3);
        return ksc((temp1-temp2+mod)%mod,temp3);
    }
    //将字符串转化为lint类型
    lint stolint(string s){
        lint res=0,mask=1;
        for(int i=s.size()-1;i>=0;i--){
            res+=(s[i]-'0')*mask;
            mask*=10;
        }
        return res;
    }
    //快速乘
    lint ksc(lint x,lint y){
        lint res=0;
        while(y>0){
            if((y&1)!=0)res=(res+x)%mod;
            x=(x<<1)%mod;
            y>>=1;
        }
        return res;
    }
    //快速幂
    lint fastpower(lint base,lint power){
        lint res=1;
        while(power>0){
            if((power&1)==1){
                res=ksc(res,base)%mod;
            }
            power>>=1;
            base=ksc(base,base)%mod;
        }return res;
    }
};

复杂度：
时间复杂度：快速乘和快速幂算法的时间复杂度都为 ,又因为快速幂和快速乘嵌套使用则总的算法时间复杂度为 ,
空间复杂度：,额外变量为常数级