首页 > 代码库 > 2014年百度之星程序设计大赛 - 初赛（第一轮） hdu Grids (卡特兰数 大数除法取余 扩展gcd)

2014年百度之星程序设计大赛 - 初赛（第一轮） hdu Grids (卡特兰数 大数除法取余 扩展gcd)

2024-07-06 03:19:33   220人阅读

题目链接

分析：打表以后就能发现时卡特兰数， 但是有除法取余。

f[i] = f[i-1]*(4*i - 2)/(i+1);

看了一下网上的题解，照着题解写了下面的代码，不过还是不明白，为什么用扩展gcd, 不是用逆元吗。。

网上还有别人的解释，没看懂，贴一下：

 (a / b) % m = ( a % (m*b)) / b

笔者注：鉴于ACM题目特别喜欢M=1000000007,为质数：

当gcd(b,m) = 1, 有性质: (a/b)%m = (a*b^-1)%m, 其中b^-1是b模m的逆元.

求出b相对于m的逆元b^(-1)，即b*(b^(-1)) = 1 (mod m)。有b*b^(-1) - km = 1，其中k是一整数. 用Extended Euclid算法可以求出`b^(-1)。然后计算a*b^(-1) mod m = ( (a%m) * (b^(-1)%m ) % m; 其值与(a/b) mod m相同

推导：a/b = x (mod m) --两边同乘一个数--> a = bx (mod m) ---x=b^-1a-> a = (b^-1) ba (mod m)

再利用b^-1*b = 1(mod m) . 所以可以得出 x = b^-1*a是成立的。

     所以 (a/b) mod m 的解与 (a*b^-1)%m的解是一样的。 而后着可以利用模对乘法的线性性

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #define LL __int64
 7 using namespace std;
 8 const int mo = 1000000000 + 7;
 9 const int maxn = 1000000 + 10;
10 LL f[maxn];
11 
12 LL exgcd(LL a,LL b,LL &x,LL &y)
13 {
14     if(b==0)
15     {
16         x=1; y=0; return a;
17     }
18     LL d = exgcd(b,a%b,x,y);
19     LL t=x;
20     x=y;
21     y=t-a/b*y;
22     return d;
23 }
24 void init()
25 {
26     int i;
27     LL x, y;
28     f[0] = f[1] = 1;
29     for(i = 2; i < maxn-5; i++)
30     {
31         f[i] = f[i-1]*(4*i-2)%mo;
32         exgcd(i+1, mo, x, y);
33         f[i] = (f[i]*((x+mo)%mo))%mo;
34     }
35 }
36 int main()
37 {
38     int t, n, ca = 1;
39     init();
40     scanf("%d", &t);
41     while(t--)
42     {
43         scanf("%d", &n);
44         printf("Case #%d:\n", ca++);
45         printf("%I64d\n", f[n]);
46     }
47     return 0;
48 }

 

 

扩展gcd:

 1 //扩展 GCD  
 2  //求x, y使得gcd(a, b) = a * x + b * y;  
 3 
 4 int extgcd(int a, int b, int & x, int & y)
 5 { 
 6     if (b == 0) { x=1; y=0; return a; } 
 7     int d = extgcd(b, a % b, x, y); 
 8     int t = x; x = y; y = t - a / b * y; 
 9     return d; 
10 }

 


联系
我们