首页 > 搜索 > DFS搜索 > HDU 3187-HP Problem-DFS-[解题报告]HOJ
2014
03-06

HDU 3187-HP Problem-DFS-[解题报告]HOJ

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

点击打开链接

/*

给出一个数n,满足P(k)=n,其中k的素因子个数<=3;n<2^31;
    欧拉函数:
        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;
}

参考:http://blog.csdn.net/yangyafeiac/article/details/8834065


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