牛牛的函数

[编程题]牛牛的函数

热度指数：2655 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

定义函数 f(x) = x^a + x^(a+1) +...+ x^(b-1) + x^b，然后在给定a和b的情况下，求f(x)%10000000033的值。

示例1

输入

1,3,2

输出

说明


f(2) = 2^1 + 2^2 + 2^3 = 14

备注:

其中0<=x,a,b<=1e9, 且 a<=b

算法知识视频讲解

C/C++

nbgao

typedef long long ll;
class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return long长整型
     */
    const ll M = 10000000033;
    ll F(ll x, ll y){
        ll s = 0;
        x %= M;
        y %= M;
        while(y){
            if(y&1){
                s += x;
                if(s>=M)
                    s -= M;
            }
            y>>=1;
            x<<=1;
            if(x>=M)
                x -= M;
        }
        return s;
    }
    ll P(ll x, ll y){
        ll s = 1;
        while(y){
            if(y&1)
                s = F(s, x);
            x = F(x, x);
            y>>=1;
        }
        return s;
    }
    long long solve(int a, int b, int n) {
        if(n==0)
            return 0;
        if(n==1)
            return b-a+1;
        ll s = (P(n, b+1)-P(n, a)+M) % M;
        ll t = P(n-1, M-2);
        return F(s ,t);
    }
};

发表于 2020-07-17 01:32:11 回复(0)

一花一世界、

题意：求(n^a + n^(a + 1) +...+n^b ) % 10000000033的值。
数据范围：

0<=x,a,b<=1e9, 且 a<=b

前置知识：同余

思路1：

由于题目数据范围巨大，故 不能使用常规幂运算 进行计算；需要使用快速幂进行加速计算，并且使用快速乘法来防止数据溢出，但是由于此方法需要遍历a ~ b，并且每次遍历有两次快速幂计算,时间复杂度为n（log（n * logn）），因此会超时。

思路2：
在思路1 的基础上，通过等比数列求和公式和求逆元进行优化。

#define LL long long
const LL mod = 10000000033;
class Solution
{
    public:
    //快速乘法
    LL quick_mul(LL a,LL b){
        a%=mod;
        b%=mod;
        LL res=0;
        while(b){
            if(b&1){
                res+=a;
                if(res>=mod)
                res-=mod;
            }
            b>>=1;
            a<<=1;
            if(a>=mod) a-=mod;
        }
        return res;
    }
    LL quick_pow(LL a, LL b){
        LL res = 1;
        while(b){
            if(b&1){
                res = quick_mul(res, a);
            }
            a = quick_mul(a, a);
            b >>= 1;
        }
        return res;
    }
    long long solve(int a,int b,int n){
        if(n==0) return 0;
        if(n==1) return b-a+1;
        LL res=(quick_pow(n, b + 1)- quick_pow(n, a)+ mod) % mod;
        //费马小定理求逆元
        LL inv=quick_pow(n - 1, mod - 2);
        return quick_mul(res,inv);
    }
};

发表于 2020-05-31 14:17:36 回复(0)

牛客874689784号

等比数列求和公式，但是**有个被除数。只能通过有一步来求；

n^a + n^(a+1) +...+ n^b

= n^a(1 + n + n^2 + ...+ n^(b-a))

=n^a(1 + n (1 + n...(1 +n)))

求两个数相乘的余数： a *b % c = (a % c) * (b %c) % c

long long solve(int a, int b, int n) {
        // write code here
    if(n == 0)
    {
        return 0;
    }

    long long s = 1;
    for(int i = 0; i < b - a; i++) {
        s = 1 + (n * s) % 10000000033;
    }

    for(int i = 0; i < a; i++)
    {
        s = (s * n) % 10000000033;
    }

    return s;

}

这么写复杂度就是O(b), 但是**超时了，不知道该怎么写了？难道和这个 10000000033有关

发表于 2020-04-10 17:36:29 回复(1)