n/φ(n)이 최소가 되며 두 값이 순열관계인 천만 이하의 n은?

 

앞의 문제와 유사하지만, 한 번 더 꼬아 난이도가 살짝 올라간 문제.

사실, 이 문제를 풀기 위해 좀 더 공부를 하고 앞의 포스팅을 수정했다.

 

\(  \phi (n)  \) 함수를 오일러가 정리한 대로 제대로 구현하지 않아도 앞의 문제는 풀 수 있었지만, 이 문제는 아니다.

일단 천만이라는 수도 무시무시한데다, 그 뒤에 \(  n  \)과 \(  \phi (n)  \)이 순열인지 여부까지 확인해야 된다.

 

코드의 기본은 앞의 내용을 (대폭 수정한 뒤에) 거의 그대로 가져왔다.

에라토스테네스의 체를 활용해서 소인수 테이블을 먼저 만드는 것도 동일하다.

순열(permutation) 여부를 확인하는 코드와 아주 약간 바뀐 규칙 외엔 거의 동일하다.

 

#include <iostream>
#include <vector>
using namespace std;

#include <Windows.h>

typedef vector<size_t> v1num_t, * pv1num_t;
typedef vector<v1num_t> v2num_t, * pv2num_t;

const static size_t MAXNUM = 10000000;

vector <BYTE> vTables(MAXNUM + 1);

//에라토스테스트의 체를 응용한 소인수 테이블 작성
void CreatePrimeDivisorsTable(v2num_t& v, const size_t max) {
    v.clear();
    v.resize(max + 1);

    for (size_t i = 2; i <= max; ++i) {
        if (v[i].empty()) {
            //i가 소수인 경우
            for (size_t n = i * 2; n <= max; n += i) {
                v[n].push_back(i);
            }
        }
    }
}

size_t CountRelativelyPrimes(const v2num_t& v, const size_t n) {
    size_t ret = n;
    const pv1num_t p = (pv1num_t) & (v[n]);
    const size_t count = p->size();

    if (!count) {
        return n - 1;
    }

    for (size_t i = 0; i < count; ++i) {
        ret = ret * ((*p)[i] - 1) / (*p)[i];
    }

    return ret;
}

bool ArePermutation(size_t a, size_t b)
{
    int counta[10] = { 0, };
    int countb[10] = { 0, };

    while (a && b) {
        ++counta[a % 10];
        a /= 10;

        ++countb[b % 10];
        b /= 10;

        if ((a && !b) || (!a && b)) {
            return false;
        }
    }

    return !memcmp(counta, countb, sizeof(counta));
}


int main()
{
    DWORD64 dw0 = GetTickCount64();

    v2num_t vTable;
    CreatePrimeDivisorsTable(vTable, MAXNUM);

    DWORD64 dw1 = GetTickCount64() - dw0;
    dw0 = GetTickCount64();

    cout << "table created (" << dw1 << " ms)" << endl;

    double min_n_phi = 0;
    size_t min_n = 0;
    size_t min_phi = 0;

    for (size_t n = 2; n <= MAXNUM; ++n) {

        if (!(n % 50000)) {
            dw1 = GetTickCount64() - dw0;
            cout << "processing " << n << "... (" << dw1 << " ms)" << endl;
        }

        const size_t phi = CountRelativelyPrimes(vTable, n);
        
        if (ArePermutation(n, phi)) {
            const double n_phi = (double)n / phi;
            if (!min_n_phi || n_phi < min_n_phi) {
                min_n_phi = n_phi;
                min_n = n;
                min_phi = phi;
            }
        }
    }

    cout << min_n << " / phi = " << min_phi << " / " << min_n_phi << endl;

    dw1 = GetTickCount64() - dw0;
    cout << "finished (" << dw1 << " ms)" << endl;
}

천만개의 수를 확인하지만, 정확한 답을 도출하는 소요시간은 단 2초.