题解 | #牛牛的函数#

题意整理

• 给定函数以及a、b的值。
• 求，结果对10000000033取余。

方法一（模拟）

1.解题思路

首先当n为0时，直接返回0。然后模拟题目给的函数进行计算，为了防止溢出，乘方运算需要使用快幂法，乘法运算使用快乘法。由于测试数据较大，这种方法运行超时。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return long长整型
     */
    //取余常数
    long mod=10000000033L;

    public long solve (int a, int b, int n) {
        //特殊情况判断
        if(n==0) return 0;
        long res=0L;
        //模拟计算f(x)
        for(int i=a;i<=b;i++){
            res=(res+fastpow(n,i))%mod;
        }
        return res;
    }

    //快幂法计算n的k次幂
    private long fastpow(long n,long k){
        long res=1L;
        while(k>0){
            //如果k是奇数，res乘以基数n
            if((k&1)==1){
                res=fastmultiply(res,n);
            }
            //每次n作平方处理，k除2
            n=fastmultiply(n,n);
            k>>=1;
        }
        return res;
    }

    //快乘法计算n*k
    private long fastmultiply(long n,long k){
        long res=0L;
        while(k>0){
            //如果k是奇数，res加上基数n
            if((k&1)==1){
                res=(res+n)%mod;
            }
            //每次n翻倍，k除2
            n=(n<<1)%mod;
            k>>=1;
        }
        return res;
    }


}

3.复杂度分析

• 时间复杂度：快乘法的时间复杂度是，于是本题中快幂法的时间复杂度是，总共需要进行次幂运算，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为。

方法二（等比数列公式+费马小定理）

1.解题思路

根据等比数列公式：，其中是首项，是等比系数，是总项数，这里。所以，根据费马小定理，，所以两边同时除以再互换位置，得：，所以最终 。
只需要计算和这两个因子，由于每次乘方和乘法运算都可能溢出，可使用快幂法和快乘法避免。

动图展示（快乘法）：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return long长整型
     */
    //取余常数
    long mod=10000000033L;

    public long solve (int a, int b, int n) {
        //特殊情况判断
        if(n==0) return 0L;
        if(n==1) return (long)(b-a+1);

        //利用等比数列和费马小定理简化运算
        long factor1=(fastpow((long)n,(long)(b+1))-fastpow((long)n,(long)a)+mod)%mod;
        long factor2=fastpow((long)(n-1),(long)(mod-2));
        return fastmultiply(factor1,factor2);
    }

    //快幂法计算n的k次幂
    private long fastpow(long n,long k){
        long res=1L;
        while(k>0){
            //如果k是奇数，res乘以基数n
            if((k&1)==1){
                res=fastmultiply(res,n);
            }
            //每次n作平方处理，k除2
            n=fastmultiply(n,n);
            k>>=1;
        }
        return res;
    }

    //快乘法计算n*k
    private long fastmultiply(long n,long k){
        long res=0L;
        while(k>0){
            //如果k是奇数，res加上基数n
            if((k&1)==1){
                res=(res+n)%mod;
            }
            //每次n翻倍，k除2
            n=(n<<1)%mod;
            k>>=1;
        }
        return res;
    }

}

3.复杂度分析

• 时间复杂度：方法一需要计算所有指数得累加和次幂运算，本方法利用费马小定理和等比数列公式，只需要计算次幂运算，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为。