2014
03-06

# HP Problem

In mathematics, the greatest common divisor (gcd), of two non-zero integers, is the largest positive integer that divides both two numbers without a remainder. For example, gcd( 10, 15 ) = 5, gcd( 5, 4 ) = 1. If gcd( k, n ) == 1 , then we say k is co-prime to n ( also , n is co-prime to k ), the totient function H(n) of a positive integer n is defined to be the number of positive integers not greater than n that are co-prime to n. In particular H(1) = 1 since 1 is co-prime to itself (1 being the only natural number with this property). For example, H (9) = 6 since the six numbers 1, 2, 4, 5, 7 and 8 are co-prime to 9. Also, we define the number of different prime of n is P (n). For example, P (4) = 1 (4 = 2*2), P (10) = 2(10 = 2*5), P (60) = 3(2*2*3*5). Now, your task is, give you a positive integer n not greater than 2^31-1, please calculate the number of k (0 < k < 2^31) satisfied that H (k) = n and P (k) <= 3(So we called HP Problem).

Each line will contain only one integer n. Process to end of file.

Each line will contain only one integer n. Process to end of file.

6

4

/*

欧拉函数：
phi(k)=k*(1-1/p1)(1-1/p2)(1-1/p3)
=(p1-1)*p1^x * (p2-1)*p2^y * (p3-1)*p3^z;
phi(1)=1;
因为n=phi(k),枚举pi-1，if(n%(pi-1)==0&&is_prime(pi))则加入pi;
然后用DFS，最大有三个数使phi(k)=n;
注意phi(1)=1;
当n==1时，有两种情况，k=1,2；

注意这里枚举（pi-1），不是n的素因子；

2013/04/22-13:36

*/

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
int n,ans;
int A[4010];
int cnt;
int ret;
int t[3];
int is_prime(int x)
{
int i;
for(i=2;i*i<=x;i++)
if(x%i==0)return 0;
return 1;
}
//从第x个开始，已经找到y个，总共需要找z个。。。
void dfs(int x,int y,int z)
{
int i;
if(y==z)
{
int tem=n;
int f=0;
for(i=0;i<z;i++)
{
if(tem%(t[i]-1)!=0)
{
f=1;break;
}
tem/=(t[i]-1);
}
if(f==0)
{
for(i=0;i<z;i++)
{
while(tem%t[i]==0)
tem/=t[i];
}
if(tem==1)ret++;
}
}
else
{
for(i=x;i<cnt;i++)
{
t[y]=A[i];
dfs(i+1,y+1,z);
}
}
}

int main()
{
while(scanf("%d",&n)!=-1)
{
if(n==1)
{
printf("2\n");
continue;
}
else
{
int i,j;
cnt=0;
//将n的素因子存入A中。
for(i=1;i*i<=n;i++)
{
if(n%i==0&&is_prime(i+1)==1)
A[cnt++]=i+1;
if(n%i==0&&is_prime(n/i+1)==1)
A[cnt++]=n/i+1;
}
sort(A,A+cnt);
//可能有重复的。。。
for(i=1;i<cnt;i++)
{
if(A[i]==A[i-1])
{
for(j=i;j<cnt-1;j++)
A[j]=A[j+1];
cnt--;
}
}
ans=0;
for(i=1;i<=3;i++)
{
ret=0;
dfs(0,0,i);
ans+=ret;
}
printf("%d\n",ans);
}
}
return 0;
}

1. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示