分析一下:
计算phi(n/k) .
必定有: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的最大素因子的范围. 继续分析一下:
由上面的分析,v<5*7*8*9.考虑等式两边2的次数,我们可以得出:
若n为偶数,则n至多含4个奇素因子;
若n为奇数,则n至多含3个奇素因子; #include <iostream>
#include <cmath>
#include <algorithm>
using namespacestd;
const double MAXD=15.0;
const int L=30000;
__int64 prime;
__int64 List;
int length;
int LLen=0;
voidInit(){
prime=2;
prime=3;
prime=7;
length=3;
for( int i=10; i<L; ++i ){
int s=int(sqrt(i));
bool flag=true;
for( int j=2; j<=s && flag; ++j )
if( i%j==0 ) flag=false;
if( flag ){
int temp=i-1;
for( int k=0; k<length; ++k ){
while( temp%prime==0 ){
temp/=prime;
}
}
if( temp==1 ){
prime=i;
}
}
}
}
int element;
doublelog_p;
int expon;
int count1=0;
void fun(double sum, int level, int maxlen, double MAXD){
if( level==maxlen+1 ){
__int64 number=1, phi=1;
for( int j=0; j<=maxlen; ++j ){
__int64 temp=element;
for( int k=0; k<expon; ++k )
number*=temp;
for( k=0; k<expon-1; ++k )
phi*=temp;
phi*=temp-1;
}
__int64 t=number;
intdig, index=0;
bool flag=true;
while( t && flag ){
dig=t%10;
t/=10;
if( dig==0 || number%dig!=0)
flag=false;
else
index++;
}
if( flag ){
int i;
introad={0,0,0,0};
intless_than10={2,3,5,7};
for( i=0; i<sizeof(road)/sizeof(road); ++i ){
for( int j=0; j<=maxlen; ++j ){
if( element==less_than10 )
road=expon;
}
}
__int64 Tot=0;
for( int k=0; k<index; ++k ){
switch( dig ){
case 1 :
Tot+=phi;
break;
case 2 :
if( road>1 )
Tot+=phi/2;
else
Tot+=phi;
break;
case 3 :
if( road>1 )
Tot+=phi/3;
else
Tot+=phi/2;
break;
case 4 :
if( road>2 )
Tot+=phi/4;
else
Tot+=phi/2;
break;
case 5 :
if( road>1 )
Tot+=phi/5;
else
Tot+=phi/4;
break;
case 6 :
if( road>1 ){
if( road>1 )
Tot+=phi/6;
else//2^k*3^1
Tot+=phi/4;
}
else{
if( road>1 )
Tot+=phi/3;
else//2^1*3^1
Tot+=phi/2;
}
break;
case 7 :
if( road>1 )
Tot+=phi/7;
else
Tot+=phi/6;
break;
case 8 :
if( road>3 )
Tot+=phi/8;
else
Tot+=phi/4;
break;
case 9 :
if( road>2 )
Tot+=phi/9;
else
Tot+=phi/6;
break;
}
}
if( Tot==number ){
printf("%I64d\n",number);
List=number;
}
}
return;
}
for( int i=1; sum+i*log_p<MAXD; ++i ){
expon=i;
fun( sum+i*log_p, level+1, maxlen, MAXD );
expon=0;
}
}
void calc(int *list, int len){
int i;
for( i=0; i<=len; ++i )
log_p=log10(element);
fun( 0, 0, len, MAXD );
}
void dfs( int index, int level ){
int i;
if( level==5 ){
calc( element, level-1 );
return;
}
for( i=index; i<length; ++i ){
__int64 temp=prime-1;
for( int k=0; k<level; ++k ){
while( temp%element==0 ) temp/=element;
}
if( temp==1 ){
element=prime;
dfs( index+1, level+1 );
calc( element, level );
element=0;
}
}
}
void start(){
int head[]={2,3,5,7};
for( int i=0; i<sizeof(head)/sizeof(head); ++i ){
element=head;
dfs( i+1, 1 );
}
}
intmain(){
Init();
start();
cout<<"========================================\n";
sort( List, List+LLen );
__int64 *end=unique( List, List+LLen );
for( int i=0; List+i!=end; ++i )
printf("%I64d\n",List);
return 0;
} 结果(1这个显然的解不在搜索范围内):
211896
61341696
141732864
219483432
1423392768
4844814336
16484622336
23362267824
28193299344
169699442688
993338339328
2344883866416
8829641374848
423732883488768 已被oeis收录: http://www.research.att.com/~njas/sequences/A158993
页:
1
[2]