HNU 11720 God Created The Integers

　　原题传送：http://acm.hnu.cn/online/?action=problem&type=show&id=11720&courseid=0

　　对于这条式子：

　　和下面的式子是等价的：

　　S_p = (p² - 1) / 2 - (p - 1) / 4

　　那么求出S_p后有r_p*S_p≡ 1 (mod p)，用扩展GCD求出r_p就行了。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 typedef __int64 LL;
 5 LL p, s;
 6 
 7 LL exgcd(LL a, LL b, LL &x, LL &y)
 8 {
 9     LL d, t;
10     if(b == 0)
11     {
12         x = 1, y = 0;
13         return a;
14     }
15     d = exgcd(b, a % b, x, y);
16     t = x, x = y, y = t - (a / b) * x;
17     return d;
18 }
19 
20 void solve(int cas)
21 {
22     s =(p * p - 1) / 24 - (p - 1) / 4;
23     LL x, y;
24     exgcd(s, p, x, y);
25     printf("Case #%d: %I64d\n", cas, (x + p) % p);
26 }
27 
28 int main()
29 {
30     int t, cas;
31     while(scanf("%d", &t) != EOF)
32     {
33         for(cas = 1; cas <= t; cas ++)
34         {
35             scanf("%I64d", &p);
36             solve(cas);
37         }
38     }
39     return 0;
40 }