hdu 3187 （歐拉函數+dfs）

/*

給出一個數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

*/

[cpp]
#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; 
} 

#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;
}