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>
   
4. 
   
5. using namespace  std;
   
6. 
   
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;
    
13. 
    
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. }
    
37. 
    
38. int     element[5];
    
39. double  log_p[5];
    
40. int     expon[5];
    
41. int     count1=0;
    
42. 
    
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.                         }
    
75.                        
    
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.                         }       
     
140.                        
     
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. }
     
154. 
     
155. 
     
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. }
     
162. 
     
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. }
     
182. 
     
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. }
     
190. 
     
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