hdu 5793 A Boring Question（2016第六场多校）

A Boring Question

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 487 Accepted Submission(s): 271

Problem Description

There are an equation.

Input

The first line of the input contains the only integer

Output

For each

Sample Input

1 2

2 3

Sample Output

Author

UESTC

题意：根据题目中规定的结算方式，给定n,m的值，求结果。

打表找规律，比赛的时候找到了还是没写出来。。因为有除法还有取模，所以要用到逆元，第一次使用逆元，找了一个模板。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #define ll long long
 6 #define mod 1000000007
 7 using namespace std;
 8 
 9 
10 ll mat(ll a,ll b)///a^b，结果对mod取膜，b的值很大的时候
11 {
12     ll c=1;
13     if(b==1) return a%mod; ///当b为1时，只剩下最后一个a
14     else if(b&1)  ///b为奇数
15         return mat(a,b-1)*a%mod; ///把单独的a拿出来
16     else ///b为偶数
17         return mat(a*a%mod,b/2)%mod; ///直接相乘，系数除以2
18 }
19 
20 ll extend_gcd(ll a,ll b,ll &x,ll &y)
21 {
22     if(a==0&&b==0) return -1;//无最大公约数
23     if(b==0){x=1;y=0;return a;}
24     ll d=extend_gcd(b,a%b,y,x);
25     y-=a/b*x;
26     return d;
27 }
28 //*********求逆元素*******************
29 //ax = 1(mod n)
30 ll mod_reverse(ll a,ll n)
31 {
32     ll x,y;
33     ll d=extend_gcd(a,n,x,y);
34     if(d==1) return (x%n+n)%n;
35     else return -1;
36 }
37 
38 ll c(ll n,ll m)
39 {
40     ll i,j,t1,t2,ans;
41     t1=((mat(m,n+1)-1)%mod+mod)%mod;
42     t2=(m-1)%mod;
43     return  t1*mod_reverse(t2,mod)%mod;
44 }
45 
46 
47 int main()
48 {
49     int T,n,m;
50     scanf("%d",&T);
51     while(T--)
52     {
53         scanf("%d%d",&n,&m);
54         ll ans=c(n,m);
55         printf("%I64d
",ans);
56     }
57     return 0;
58 }