杰 & C++ & Python & DM

POJ 2115 C Looooops解题报告

     题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2115
     本题是一道数论的入门题,模型为求 ax = b (mod n),本题中,a = C, b = B-A, n = 2^k

     因此使用求解模线性方程算法modular_linear。关于算法的详细原理可参见欧几里德_扩展欧几里德_模线性方程,这篇blog对相关的算法给出了详细的证明,推荐。


     下面给出本题的代码,本题有几点需要注意:
     1.需要使用64位整数计算,因为2^32对普通整数会溢出;
     2.第48行,在求n时,因为在C++中,默认0x01为int型,如果不加强制转换,那么移位后会溢出;所以强制类型转换是必须的。


 1 #include <cstdio>
 2 typedef long long Int64;
 3 
 4 // ax + by = d   其中d = gcd(a,b)
 5 Int64 extend_euclid(Int64 a, Int64 b, Int64& x, Int64& y)
 6 {
 7     if(b == 0)
 8     {
 9         x = 1;
10         y = 0;
11         return a;
12     }
13     else
14     {
15         Int64 gcd, t;
16         gcd = extend_euclid(b, a%b, x, y);
17         
18         t = x;
19         x = y;
20         y = t - a / b * y;
21         return gcd;
22     }
23 }
24 
25 // ax = b mod n
26 Int64 modular_linear(Int64 a, Int64 b, Int64 n)
27 {
28     Int64 x = 0;
29     Int64 y = 0;
30     Int64 d = 0;
31 
32     d = extend_euclid(a,n,x,y);
33     
34     if(b % d == 0)
35     {
36         x = (x * (b / d)) % n + n;
37         return x % (n/d);
38     }
39     return -1;
40 }
41 
42 int main()
43 {
44     Int64 A,B,C,k;
45     
46     while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k),k)
47     {
48         Int64 n = (Int64)0x01 << k;
49         
50         Int64 res = modular_linear(C, B-A, n);
51         if(res == -1)
52         {
53             printf("FOREVER\n");
54         }
55         else
56         {
57             printf("%lld\n",res);
58         }
59     }
60     
61     return 0;
62 }
63 

                



posted on 2010-04-11 16:41 jaysoon 阅读(303) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2023年2月>
2930311234
567891011
12131415161718
19202122232425
2627281234
567891011

导航

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

收藏夹

C++

搜索

最新评论

阅读排行榜

评论排行榜