Puzzle 500. 211896

medie2005

分析一下: 计算$phi(n/k)$ [1<=k<=9]. 必定有:$phi(n/k)=phi(n)*1/t$. [其中,1<=t<=9, t由k以及n的素分解决定]. 因此,如果n是一个解,那么,必要条件是: $n=phi(n)*u/v$. [其中,$u/v$是$1/1,1/2,1/3,...,1/9$中选若干个的和] 而根据u的大小,我们可以断定n的最大素因子的范围.

medie2005

继续分析一下: 由上面的分析,v<5*7*8*9.考虑等式两边2的次数,我们可以得出: 若n为偶数,则n至多含4个奇素因子; 若n为奇数,则n至多含3个奇素因子;

medie2005

1. #include <iostream>
2. #include <cmath>
3. #include <algorithm>
5. using namespace std;
7. const double MAXD=15.0;
8. const int L=30000;
9. __int64 prime[L];
10. __int64 List[100];
11. int length;
12. int LLen=0;
14. void Init(){
15. prime[0]=2;
16. prime[1]=3;
17. prime[2]=7;
18. length=3;
19. for( int i=10; i<L; ++i ){
20. int s=int(sqrt(i));
21. bool flag=true;
22. for( int j=2; j<=s && flag; ++j )
23. if( i%j==0 ) flag=false;
24. if( flag ){
25. int temp=i-1;
26. for( int k=0; k<length; ++k ){
27. while( temp%prime[k]==0 ){
28. temp/=prime[k];
29. }
30. }
31. if( temp==1 ){
32. prime[length++]=i;
33. }
34. }
35. }
36. }
38. int element[5];
39. double log_p[5];
40. int expon[5];
41. int count1=0;
43. void fun(double sum, int level, int maxlen, double MAXD){
44. if( level==maxlen+1 ){
45. __int64 number=1, phi=1;
46. for( int j=0; j<=maxlen; ++j ){
47. __int64 temp=element[j];
48. for( int k=0; k<expon[j]; ++k )
49. number*=temp;
50. for( k=0; k<expon[j]-1; ++k )
51. phi*=temp;
52. phi*=temp-1;
53. }
54. __int64 t=number;
55. int dig[100], index=0;
56. bool flag=true;
57. while( t && flag ){
58. dig[index]=t%10;
59. t/=10;
60. if( dig[index]==0 || number%dig[index]!=0 )
61. flag=false;
62. else
63. index++;
64. }
65. if( flag ){
66. int i;
67. int road[4]={0,0,0,0};
68. int less_than10[4]={2,3,5,7};
69. for( i=0; i<sizeof(road)/sizeof(road[0]); ++i ){
70. for( int j=0; j<=maxlen; ++j ){
71. if( element[j]==less_than10[i] )
72. road[i]=expon[j];
73. }
74. }
76. __int64 Tot=0;
77. for( int k=0; k<index; ++k ){
78. switch( dig[k] ){
79. case 1 :
80. Tot+=phi;
81. break;
82. case 2 :
83. if( road[0]>1 )
84. Tot+=phi/2;
85. else
86. Tot+=phi;
87. break;
88. case 3 :
89. if( road[1]>1 )
90. Tot+=phi/3;
91. else
92. Tot+=phi/2;
93. break;
94. case 4 :
95. if( road[0]>2 )
96. Tot+=phi/4;
97. else
98. Tot+=phi/2;
99. break;
100. case 5 :
101. if( road[2]>1 )
102. Tot+=phi/5;
103. else
104. Tot+=phi/4;
105. break;
106. case 6 :
107. if( road[0]>1 ){
108. if( road[1]>1 )
109. Tot+=phi/6;
110. else//2^k*3^1
111. Tot+=phi/4;
112. }
113. else{
114. if( road[1]>1 )
115. Tot+=phi/3;
116. else//2^1*3^1
117. Tot+=phi/2;
118. }
119. break;
120. case 7 :
121. if( road[3]>1 )
122. Tot+=phi/7;
123. else
124. Tot+=phi/6;
125. break;
126. case 8 :
127. if( road[0]>3 )
128. Tot+=phi/8;
129. else
130. Tot+=phi/4;
131. break;
132. case 9 :
133. if( road[1]>2 )
134. Tot+=phi/9;
135. else
136. Tot+=phi/6;
137. break;
138. }
139. }
141. if( Tot==number ){
142. printf("%I64d\n",number);
143. List[LLen++]=number;
144. }
145. }
146. return;
147. }
148. for( int i=1; sum+i*log_p[level]<MAXD; ++i ){
149. expon[level]=i;
150. fun( sum+i*log_p[level], level+1, maxlen, MAXD );
151. expon[level]=0;
152. }
153. }
156. void calc(int *list, int len){
157. int i;
158. for( i=0; i<=len; ++i )
159. log_p[i]=log10(element[i]);
160. fun( 0, 0, len, MAXD );
161. }
163. void dfs( int index, int level ){
164. int i;
165. if( level==5 ){
166. calc( element, level-1 );
167. return;
168. }
169. for( i=index; i<length; ++i ){
170. __int64 temp=prime[i]-1;
171. for( int k=0; k<level; ++k ){
172. while( temp%element[k]==0 ) temp/=element[k];
173. }
174. if( temp==1 ){
175. element[level]=prime[i];
176. dfs( index+1, level+1 );
177. calc( element, level );
178. element[level]=0;
179. }
180. }
181. }
183. void start(){
184. int head[]={2,3,5,7};
185. for( int i=0; i<sizeof(head)/sizeof(head[0]); ++i ){
186. element[0]=head[i];
187. dfs( i+1, 1 );
188. }
189. }
191. int main(){
192. Init();
193. start();
194. cout<<"========================================\n";
195. sort( List, List+LLen );
196. __int64 *end=unique( List, List+LLen );
197. for( int i=0; List+i!=end; ++i )
198. printf("%I64d\n",List[i]);
199. return 0;
200. }

复制代码

medie2005

结果(1这个显然的解不在搜索范围内): 211896 61341696 141732864 219483432 1423392768 4844814336 16484622336 23362267824 28193299344 169699442688 993338339328 2344883866416 8829641374848 423732883488768

medie2005

已被oeis收录: http://www.research.att.com/~njas/sequences/A158993