[数论]POJ 3358

传送门
这题首先你要知道化成二进制的小数可以每次分子2,再对分母求余,然后分母不变,这样就能得到所有的二进制小数了.知道了这一点之后,剩下的就只是一个欧拉函数的问题了.
题中给出p/q.需要求出r和s,那么按照上面的思想,可以转化成p2^(r+s)=p2^r(mod q)继续化变成
q|p2^r(2^s-1).到了这里我们就基本没啥问题了,首先可以把p和q都除掉gcd(p,q)使之变成p’,q’.那么就变成了q’|p’2^r(2^s-1)—–>q’|2^r(2^s-1)(I)[因为没有p’和q’公因子了可以直接忽略p’],这里我们再把q’和2^r的最大公约数除掉,也就是q’一直除2知道不能除尽位置,这里就可以算法r了.算出r之后上面的式子I就再次变成了q’|(2^s-1)这里就熟悉了,我们转化成2^s=1(mod q’),首先我们知道gcd(2,q’)=1,然后2^phi(q’)=1(mod q’),对于k|q’,2^k=1(mod q’)也是有可能的,这里可以参照原根,因为如果对于2^k=1(mod q’)中最小的k==phi(q’)那么2就是q’的一个原根.好了,到这里本题基本就结束了.只需要求出q’的欧拉函数,然后对phi(q’)的每个因子都去试验下p2^(r+k) ?= p*2^r(mod q)如果等式成立,那么k就是答案(这里的k是phi(q’)的最小约数)代码如下:



1. #include
2. #include
3. #include
4. #include
5. int64 p,q,s,pr,r;
6. int64 prime[6760],idx;
7. int64 my_map[36][2],total;
8. /初始化素数 用来分解一个数/
9. void init_prime()
10. {
11. int64 i,j;
12. char p[65536];
13. memset(p,0,sizeof(p));
14. prime[0]=2;
15. idx = 1;
16. for(i=4;i<65536;i+=2) <="" span="">
17. {
18. p[i]=1;
19. }
20. for(i=3;i<65536;i +="2)" <="" span="">
21. {
22. if(0 == p[i])
23. {
24. prime[idx]=i;
25. idx++;
26. for(j = ii;j <65536; j += 2i)
27. {
28. p[j]=1;
29. }
30. }
31. }
32. }
33. /两个数的最大公约数/
34. int64 gcd(int64 a,int64 b)
35. {
36. int64 t;
37. while(b)
38. {
39. t = a;
40. a = b;
41. b = t%b;
42. }
43. return a;
44. }
45. /求n的欧拉函数/
46. int64 get_phi(int64 n)
47. {
48. int64 ret=1;
49. int64 i;
50. for(i=2;ii<=n;i++)
51. {
52. if(0 == (n%i))
53. {
54. n /= i;
55. ret = i-1;
56. while(0 == (n%i))
57. {
58. n /= i;
59. ret = i;
60. }
61. }
62. }
63. if(n > 1)
64. ret = (n-1);
65. return ret;
66. }
67. /快速幂取模/
68. int64 pow_mod(int64 a,int64 b,int64 c)
69. {
70. int64 ret=1;
71. while(b)
72. {
73. if(b1)
74. ret = (reta)%c;
75. b >>= 1;
76. a = (aa)%c;
77. }
78. return ret;
79. }
80. /dfs枚举q’的所有因子/
81. void dfs(int64 val,int64 now)
82. {
83. int64 t,j;
84. if(now == total)
85. {
86. t = pow_mod(2,r+val,q);
87. if((pt)%q == pr)
88. {
89. if(val < s)
90. s = val;
91. }
92. return ;
93. }
94. j = 1;
95. for(t = 0;t<=my_map[now][1];t++)
96. {
97. dfs(valj,now+1);
98. j = jmy_map[now][0];
99. }
100. }
101. /算法主体/
102. void work()
103. {
104. int64 p1,q1,tq;
105. int64 e,i;
106. tq = gcd(p,q);
107. p1 = p/tq;
108. q1 = q/tq;
109. tq = q;
110. r = 1;
111. /求r的值/
112. while(0 == (tq1))
113. {
114. r++;
115. tq >>= 1;
116. }
117.
118. e = get_phi(tq);
119. total = 0;
120. s = e;
121. /分解phi(tq)/
122. for(i=0;i
123. {
124. if(0 == (e%prime[i]))
125. {
126. my_map[total][0] = prime[i];
127. my_map[total][1] = 0;
128. while(0 == (e%prime[i]))
129. {
130. e /= prime[i];
131. my_map[total][1]++;
132. }
133. total++;
134. }
135. }
136. pr = (ppow_mod(2,r,q))%q;
137. dfs(1,0);
138. printf(“%I64d,%I64d\n”,r,s);
139. }
140.
141. int main(void)
142. {
143. int i=1;
144. init_prime();
145. while(EOF != scanf(“%I64d/%I64d”,p,&q))
146. {
147. //printf(“%I64d\n”,(p*pow_mod(2,8,q))%q);
148. printf(“Case #%d: “,i);
149. i++;
150. work();
151. }
152. return 0;
153. }

Comments

▲