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 }

轉載于:https://www.cnblogs.com/huangfeihome/archive/2012/10/06/2713070.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/260345.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/260345.shtml
英文地址，請注明出處：http://en.pswp.cn/news/260345.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！