Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value of n, 1 n
107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
题目大意：
欧拉函数φ(n)（有时也叫做phi函数）可以用来计算小于等于n 的数字中与n互质的数字的个数。例如，因为1,2,4,5,7,8全部小于9并且与9互质，所以φ(9)=6。
数字1被认为与每个正整数互质，所以 φ(1)=1。
有趣的是，φ(87109)=79180，可以看出87109是79180的一个排列。
对于1 n
107，并且φ(n)是 n 的一个排列的那些 n 中，使得 n/φ(n) 取到最小的 n 是多少？
//（Problem 70）Totient permutation
// Completed on Tue, 18 Feb 2014, 11:06
// Language: C11
//
// 版权所有（C）acutus (mail: acutus@126.com)
// 博客地址：http://www.cnblogs.com/acutus/
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<stdbool.h> #define N 10000000 int phi[N]; //数组中储存每个数的欧拉数 int cmp(const void * a, const void * b)
{
return (*(char *)a - *(char *)b);
} void genPhi(int n)//求出比n小的每一个数的欧拉数(n-1的)
{
int i, j, pNum = ;
memset(phi, , sizeof(phi)) ;
phi[] = ;
for(i = ; i < n; i++)
{
if(!phi[i])
{
for(j = i; j < n; j += i)
{
if(!phi[j])
phi[j] = j;
phi[j] = phi[j] / i * (i - );
}
}
}
} int fun(int n) //计算整数n的位数
{
return (log10(n *1.0) + );
} bool compare(int n, int m) //判断两整数是否其中一个是另一个的排列数
{
int i, L1, L2;
char from[], to[];
sprintf(from, "%lld", m);
sprintf(to, "%lld", n);
L1 = strlen(from);
L2 = strlen(to);
qsort(from, L1, sizeof(from[]), cmp);
qsort(to, L2, sizeof(to[]), cmp);
return !strcmp(from, to);
} void solve()
{
int i, j, count, k;
double min, t;
min = 10.0;
for(i = ; i < N; i++) {
if((fun(i) == fun(phi[i])) && compare(i, phi[i])) {
t = i * 1.0 / phi[i];
if(t < min) {
min = t;
k = i;
}
}
}
printf("%d\n", k);
} int main()
{
genPhi(N);
solve();
return ;
}
|
Answer:
|
8319823 |