HDU 3307 欧拉函数
这题首先可以把a(n)的公式推出来,a(n)=x^na(0)+Y(x^n-1)/(x-1).然后a(n)%a(0)=0也就是[x^na(0)+Y(x^n-1)/(x-1)]%a(0)=0那么x^na(0)这一项省略得到Y(x^n-1)/(x-1)%a(0)=0.我们设k=Y/(x-1).因为题中保证(x-1)|Y.所以k是整数.这样就得到k(x^n-1)=0(mod a(0)).也就是k(x^n-1)=m*a(0),其中m>=0且是整数.两边同时除掉gcd(k,a(0))之后就变成了(x^n-1)=0(mod a(0)).也就是x^n=1(mod a(0))[现在的a(0)是原来的a(0)/gcd(a(0),k)].我们知道如果gcd(x,a(0))==1那么x^phi(a(0))=1(mod a(0)).如果不等于1就无解.但是当gcd(x,a(0))=1的时候是不是Phi(a(0))就是题目的答案呢?显然不是,就想4^4=1(mod 5)但是4^2=1(mod 5).但是我们知道如果对于一个数t,x^t=1(mod a(0))的话,那么t|phi(a(0)).这样我们就好办了.只需要枚举phi(a(0))的所有因子就OK了,然后取最小的那个使得x^t=1(moid a(0))的因子就是本题答案了.代码如下:
1. /
2. ID:klion26
3. LANG:C
4. TASK:HDU_3307
5. /
6. #include
7. #include
8. #include
9. #include
10.
11. int64 eular[66000];
12. int64 idx,prime[6600];
13. int64 x,y,a0;
14. int64 total,num[16][2];
15. int64 min;
16. void init()
17. {
18. int64 i,j;
19. int64 n=65536;
20. memset(eular,0,sizeof(eular));
21. eular[1]=1;
22. for(i=2;i<=n;i++)
23. {
24. if(0==eular[i])
25. {
26. prime[idx]=i;
27. idx++;
28. for(j=i;j<=n;j+=i)
29. {
30. if(0 == eular[j])
31. eular[j]=j;
32. eular[j] /= i;
33. eular[j] *= (i-1);
34. }
35. }
36. }
37. }
38. int64 get_eular(int64 n)
39. {
40. int64 ret;
41. int64 i,k;
42. if(n<=65536)
43. return eular[n];
44. for(i=0;i
45. {
46. if(0 == (n%prime[i]))
47. break
48. }
49. if(i == idx)
50. return n-1;
51. k = n/prime[i];
52. if(0 == (k%prime[i]))
53. ret = prime[i]get_eular(k);
54. else
55. ret = (prime[i]-1)get_eular(k);
56. return ret;
57. }
58. int64 gcd(int64 a,int64 b)
59. {
60. int tmp;
61. if(a < b)
62. {
63. tmp = a;
64. a = b;
65. b = tmp;
66. }
67. while(b)
68. {
69. tmp = a;
70. a = b;
71. b = tmp%b;
72. }
73. return a;
74. }
75. int64 pow_mod(int64 a,int64 b,int64 c)
76. {
77. int64 ret = 1;
78. a %= c;
79. while(b)
80. {
81. if(b1)
82. {
83. ret = (reta)%c;
84. }
85. b >>= 1;
86. a = (aa)%c;
87. }
88. return ret;
89. }
90. void dfs(int64 now,int64 level)
91. {
92. int64 i,j;
93. if(level == total)
94. {
95. if((1 == pow_mod(x,now,a0)))
96. {
97. if(now < min)
98. {
99. min = now;
100. }
101. }
102. return ;
103. }
104. j = 1;
105. for(i=0;i<=num[level][1];i++)
106. {
107. now = j;
108. dfs(now,level+1);
109. now /= j;
110. j = num[level][0];
111. }
112. }
113. void work()
114. {
115. __int64 en,i,j;
116. j = y/(x-1);
117. i = gcd(j,a0);
118. a0 /= i;
119. if(1 != gcd(a0,x))
120. {
121. printf(“Impossible!\n”);
122. return ;
123. }
124. en=get_eular(a0);
125. total=0;
126. min = en;
127. for(i=0;i
128. {
129. if(0 == (en%prime[i]))
130. {
131. num[total][0]=prime[i];
132. j=0;
133. while(0 == (en%prime[i]))
134. {
135. j++;
136. en /= prime[i];
137. }
138. num[total][1] = j;
139. total++;
140. }
141. if(1 == en)
142. break
143. }
144. if(en > 1)
145. {
146. num[total][0]=en;
147. num[total][1] = 1;
148. total++;
149. }
150. dfs(1,0);
151. printf(“%I64d\n”,min);
152. }
153. int main(void)
154. {
155. init();
156. while(EOF != scanf(“%I64d%I64d%I64d”,x,&y,&a0))
157. {
158. if(0 == y)
159. printf(“1\n”);
160. else
161. work();
162. }
163. return 0;
164. }
