HDOJ 5793 A Boring Question 数学+猜想

看到这个式子，心里就很不爽啊！

这要怎么搞啊！

先贴个证明的方法：猜想的公式的证明

首先呢，题目中其实给的是三组样例哦

n=1，m=3，ans=4

n=1，m=2，ans=3

n=2，m=3，ans=13

有没有发现，当n变大一位的时候，ans变大得很多很多

尤其是n和m都是这么大的值的时候，这个题必定是个公式题

那么，我们来猜测一发公式吧！

看到ans=13，会想到13是怎么来的？

           27-1

13 = ---------  对吧

              2

因为13是个素数，所以这是它唯一可以分解的形式了

那么看分子，27是个什么？3的3次方，那么跟n=2，m=3有什么关系呢？

再看看ans=4

            9-1

4 = --------------

              2

ans=3

            4-1

3 = --------------

              1

所以可以猜测得到公式了：

               m^(n+1) - 1

ans = ---------------------

                    m-1

注意，这个值是很大的数值

首先要有快速幂

然后，因为有取模运算，所以除法要变成乘法，也就是说：需要计算（m-1）对于1e9+7这个素数的逆元

也就是（m-1）^(p-2)次方

素数的一个性质，当p为素数时，x^(p-1)同余于1对于任意x都成立

代码如下：

#include<bits/stdc++.h>
using namespace std;

#define LL __int64
LL n,m,mod,ans;

LL quickpow(LL a,LL b,LL p){
    LL ans=1;
    while(b){
        if (b%2) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

LL getniyuan(LL x,LL p,LL mod){
    return quickpow(x,p-2,mod);
}

int main(){
    mod=1e9+7;
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%I64d%I64d",&n,&m);
        LL fenzi=(quickpow(m,n+1,mod)+mod-1)%mod;
        LL niyuan=getniyuan(m-1,mod,mod);
        printf("%I64d\n",fenzi*niyuan%mod);
    }
    return 0;
}