permeuler

#include <fstream>
using namespace std;

int Phi(int n)
{
    int d;
    unsigned long long int nrp=n,prod=1;
    if(n%2==0)
    {
        while(n%2==0)
            n/=2;
        nrp*=(2-1),prod*=2;
    }
    d=3;
    while(n>1)
    {
        if(n%d==0)
        {
            while(n%d==0)
                n/=d;
            nrp*=d-1,prod*=d;
        }
        else
            d+=2;
        if(n>1&&d*d>n)
        {
            nrp*=n-1,prod*=n;
            break;
        }
    }
    return (int) (nrp/prod);
}

bool perm(int x,int y)
{
    if(x==y)
        return false;
    int Cx[10],Cy[10];
    for(int i=0;i<=9;++i)
        Cx[i]=Cy[i]=0;
    while(x)
        ++Cx[x%10],x/=10;
    while(y)
        ++Cy[y%10],y/=10;
    for(int i=0;i<=9;++i)
        if(Cx[i]!=Cy[i])
            return false;
    return true;
}

int main()
{
    int x,sol=0;
    double Min=1000000000;
    ifstream f("permeuler.in");
    while(f>>x)
    {
        int p=Phi(x);
        if(perm(x,p))
        {
            double t=1.0*x/p;
            if(t<Min)
                Min=t,sol=x;
        }
    }
    ofstream g("permeuler.out");
    g<<sol;
    return 0;
}