题解 | #牛牛的函数2#

题意整理

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

方法一（模拟）

1.解题思路

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

2.代码实现

import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 
     * @param sa string字符串 
     * @param sb string字符串 
     * @param n int整型 
     * @return long长整型
     */
    //定义要用到的一些常量
    final BigInteger MOD=new BigInteger("10000000033");
    final BigInteger ZERO=new BigInteger("0");
    final BigInteger ONE=new BigInteger("1");
    final BigInteger TWO=new BigInteger("2");

    public long solve (String sa, String sb, int n) {
        //特殊情况处理
        if(n==0) return 0L;
        BigInteger res=ZERO;
        //定义函数计算要用到的大数
        BigInteger a=new BigInteger(sa);
        BigInteger b=new BigInteger(sb);
        BigInteger x=new BigInteger(String.valueOf(n));
        //模拟函数计算
        for(BigInteger i=a;i.compareTo(b)==-1;i=i.add(ONE)){
            res=res.add(((i.add(ONE).mod(MOD)).multiply(fastpow(x,i)).mod(MOD))).mod(MOD);
        }

        return res.longValue();
    }

    //大数快幂法
    private BigInteger fastpow(BigInteger n,BigInteger k){
        BigInteger res=ONE;
        while(!k.equals(ZERO)){
            //如果是奇数，res需要乘以基数n
            if(k.mod(TWO).longValue()==1L){
                res=res.multiply(n).mod(MOD);
            }
            //每次n作平方处理，k减半
            n=n.multiply(n).mod(MOD);
            k=k.divide(TWO);
        }
        return res;
    }
}

3.复杂度分析

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

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

1.解题思路

已知，等式两边同时乘以x得：，然后错位相减，可得：，可以发现，右边多项式的前项是等比数列。
利用等比数列公式，化简之后的函数是：，然后根据费马小定理，，所以两边同时除以再互换位置，得：，于是，可转化为。

动图展示（快幂法）：

2.代码实现

import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 
     * @param sa string字符串 
     * @param sb string字符串 
     * @param n int整型 
     * @return long长整型
     */
    //定义要用到的一些常量
    final BigInteger MOD=new BigInteger("10000000033");
    final BigInteger ZERO=new BigInteger("0");
    final BigInteger ONE=new BigInteger("1");
    final BigInteger TWO=new BigInteger("2");

    public long solve (String sa, String sb, int n) {
        //特殊情况处理
        if(n==0) return 0L;
        BigInteger res=ZERO;
        //定义函数计算要用到的大数
        BigInteger a=new BigInteger(sa);
        BigInteger b=new BigInteger(sb);
        BigInteger x=new BigInteger(String.valueOf(n));

        //n等于1时，只需计算a+1到b之间所有数字的和
        if(n==1){
            return a.add(b).mod(MOD).add(ONE).mod(MOD)
                    .multiply(b.subtract(a).mod(MOD))
                    .divide(TWO).mod(MOD).longValue();
        }

        //x-1对应的大数
        BigInteger div=x.subtract(ONE).add(MOD).mod(MOD);
        //(bx-b-1)*x^b对应的大数
        BigInteger f1=b.multiply(x).subtract(b).subtract(ONE).add(MOD).mod(MOD)
                       .multiply(fastpow(x,b)).mod(MOD);
        //(ax-a-1)*x^a对应的大数
        BigInteger f2=a.multiply(x).subtract(a).subtract(ONE).add(MOD).mod(MOD)
                       .multiply(fastpow(x,a)).mod(MOD);

        //推导出来的公式
        res=inv(f1.subtract(f2).add(MOD).mod(MOD),div.pow(2).mod(MOD));
        return res.longValue();
    }

    //利用费马小定理重写大数除法运算，防止运算不准
    private BigInteger inv(BigInteger a,BigInteger b){
        return a.multiply(fastpow(b,MOD.subtract(TWO))).mod(MOD);
    }

    //大数快幂法
    private BigInteger fastpow(BigInteger n,BigInteger k){
        BigInteger res=ONE;
        while(!k.equals(ZERO)){
            //如果是奇数，res需要乘以基数n
            if(k.mod(TWO).longValue()==1L){
                res=res.multiply(n).mod(MOD);
            }
            //每次n作平方处理，k减半
            n=n.multiply(n).mod(MOD);
            k=k.divide(TWO);
        }
        return res;
    }
}

3.复杂度分析

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