hdu3187 HP Problem

g87616758

Problem Description

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).



Input

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



Output

For each case, output the answer in one line.



Sample Input



6



Sample Output



4

　　思路：给定n为在[1,2^31-1]范围内有多少个数满足 H(k)=n&& P(k)<=3;
　　H（k)为k的欧拉函数；P(K)为k中所含质因子的种类个数；
　　欧拉公式：如果k=p1^q1 *P2^q2*....*pm^qm;
　　则H(k)=k*(p1-1)*(p2-1)...(pm-1)/(p1*p2*p3*p4...pm)
　　如果已知H（k）以及k中质因子（p1, p2, p3, p4,..pm)则可以唯一确定一个k=H(k)*(p1*p2*...*pm)/((p1-1)*(p2-1)...*(pm-1))
　　于是对于n，如果找到了质因子集合{p1,p2,...,pm}( m<=3)则等于找到了一个k；
　　同时这样的质因子集合满足
　　n%(pi-1)==0&&n 不含集合外的其他质因子；同时求得的K应小于2^31;
　　由于m<=3可以枚举具有上述性质的质因子集合来得到答案；
　　n为1时，有2个，H(1)=1这种特殊情况要考虑。
　　(真心看不懂啊……）


View Code


#include<stdio.h>
#include<queue>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<memory>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<malloc.h>
#include<iostream>
using namespace std;
typedef __int64 ll;
#define N 100000
#define M_F 1000
const ll base=2147483648;
int tag[N];
ll prime[N/10],cnt;
ll p[M_F],q[M_F],num;
ll a[M_F],m;
ll ans,n,pr[10],t;
void get_prime()
{
int i,j;
memset(tag,0,sizeof(tag));
for(i=2;i*i<N;i++)
if(!tag)
{
for(j=2;j*i<N;j++)
tag[j*i]=1;
}
for(i=2,cnt=0;i<N;i++)
if(tag==0)prime[cnt++]=i;
}
void factor()
{
int i;
ll tmp=n;
for(num=0,i=0;i<cnt&&prime*prime<=n;i++)
if(n%prime==0)
{
p[num]=prime;
q[num]=0;
while(n%prime==0)
{
q[num]++;
n/=prime;
}
num++;
}
if(n>1)
{
p[num]=n;
q[num++]=1;
}
n=tmp;
}
int Is_Ok(ll cur)
{
int i;
cur++;
for(i=0;i<cnt&&prime*prime<=cur;i++)
if(cur%prime==0)return 0;
return 1;
}
void dfs(ll cur,int idx)
{
ll tmp=1;
if(idx>=num)
{
if(Is_Ok(cur))a[m++]=cur;
return ;
}
for(int i=0;i<=q[idx];i++)
{
dfs(cur*tmp,idx+1);
tmp=tmp*p[idx];
}
}
int judge()
{
ll ret,tmp;
ret=n;
int i;
for(i=0;i<t;i++)
{
if(ret%(pr-1))return 0;
else ret/=(pr-1);
}
for(i=0;i<t;i++)
{
ret=ret*pr;
if(ret>=base||ret<0)return 0;
}
//tmp=ret;
ret=n;
for(i=0;i<t;i++)
{
ret/=(pr-1);
}
for(i=0;i<t;i++)
while(ret%pr==0)ret/=pr;
//if(ret==1)cout<<tmp<<endl;
return (ret==1);
}
void dfs1(int idx,int k)
{
if(k>3)return ;
else
{
if(k)
{
t=k;
ans+=judge();
}
int i;
for(i=idx;i<m;i++)
{
pr[k]=a+1;
dfs1(i+1,k+1);
}
}
}
int main()
{
get_prime();
while(scanf("%I64d",&n)!=EOF)
{
factor();
m=0;
dfs(1,0);
ans=0;
dfs1(0,0);
if(n==1)ans++;
printf("%I64d\n",ans);
}
return 0;
}