Number of Proper Fractions with Denominator d (4kyu)

https://www.codewars.com/kata/55b7bb74a0256d4467000070/cpp

풀기 전부터 느낌이 쎄한 문제였습니다.
보통 이런 문제는 공식이 있거든요.
3일 동안 삽질해서 다른 답들을 보니 역시 공식이 존재하는 문제였습니다. 더 작은 코드로 더 빨리 되네요. 당연한 거겠죠.

문제는 다음과 같습니다.
큰 숫자(long long 타입) n이 있고, 이 보다 작은 숫자(1,..,n-1)를 분모로 하고 n을 분자로 할 때, 이 분수가 나누어질 수 없는 경우를 count하라는 문제입니다.

$n = 6$이라면, $\frac{1}{6}, \frac{5}{6}$ 만 해당되므로 정답은 2가 되는 식입니다. 나머지는 $\frac{2}{6}=\frac{1}{3},\frac{3}{6}=\frac{1}{2},\frac{4}{6}=\frac{2}{3}$ 이렇게 나누어질 수 있으므로 제외됩니다.

일단 저의 접근 법은 다음과 같았습니다.
나누어지는 조건을 본다면, 동일한 소인수(Prime Factor)를 가진다고 보고, n보다 작은 숫자 중 n의 소인수를 가지지 않는 항목만 빼기로 했습니다. 예를 들어, 6의 경우 소인수는 2, 3입니다. 그리고 위에서 나누어진 경우인 2, 3, 4는 모두 2 또는 3을 소인수로 가지고 있습니다.
이런 부분만 제외하겠다는 것이 기본 접근 법입니다.

이를 위해서 우선은 소인수 분해를 하는 메소드를 아래와 같이 만들었습니다.

소인수 변수인 d를 2부터 시작해서 계속 업데이트를 해가며, 나머지가 0인 경우를 찾는 방식입니다.
속도를 빠르게 하기 위해서 t라는 변수를 두어, d로 나누어질 때, n도 같이 나누어 점점 크기를 줄여나갔습니다.
그리고 종료 조건 또한 d가 sqrt(t)보다는 커질 수 없도록 했습니다. $3 \times 5, 4 \times 4$까지 했으면, $5 \times 3$은 할 필요가 없다는 의미에서 입니다. 일단 이렇게 하면 소인수분해를 하는 시간을 대폭 줄일 수 있습니다.

void primeFactor(const long long &n, std::vector<long long> &ret)
{
    ret.clear();

    long long t = n;
    long long d = 2;
    float sqrtT = sqrt(float(t));
    while (true)
    {
        if (n != d && t % d == 0)
        {
            t /= d;
            sqrtT = sqrt(float(t));
            ret.push_back(d);

            while (true)
            {
                if (t % d == 0)
                {
                    t /= d;
                }
                else
                    break;
            }
        }
        else
        {
            d++;

            if (d % 2 == 0)
                d++;
        }

        if ((float)d > sqrtT || t < 2 * d || n < d * 2)
        {
            if ((ret.size() > 0 && ret.back() < t) && t != n)
                ret.push_back(t);
            break;
        }
    }
}

n에 대해서 소인수 분해가 끝났으면, 이제는 n보다 작은 수에 대해서 구해진 소인수로 나눌 수 있는 지를 판단해야 합니다.

brute하게 1~n-1까지 모든 수에 대해서 n의 소인수들로 나누어보아, 나누어지지 않는 경우만 세면 됩니다. 하지만 이 문제는 n이 long long 타입으로 올 수 있기 때문에 굉장히 시간이 많이 걸릴 수 있습니다.
그래서 생각한 방식은 n의 소인수 각각으로 나눌 수 있는 개수를 찾았습니다. 예를 들어서 20는 소인수가 2와 5입니다. 2로 나눌 수 있는 개수는 $20/2 = 10$이며 $20/5 = 4$입니다. 그럼 14개가 나오니 정답은 $20-14=6$ 이렇게 하면 될 거 같지만 중복 요소도 존재합니다. 10과 20이죠. 중복을 고려하면 답은 8이 됩니다. 일단 이 방식을 사용하면 전체를 순회할 필요가 없으니 속도는 빠르나 중복 요소 처리가 필수입니다. 그래서 다음 알고리즘을 고안했습니다. 점점 산으로 가고 있습니다. 이때부터 사실 망쳤다는 느낌이 들었지만 끝까지 가보기로 했습니다. Engineering은 일단 돌아가게 만들자가 기본이니깐요..

아래 그림은 3개 원이 중복이 되는 경우인데,
이 문제에서 소인수가 3개인 경우라고 보겠습니다.
3개 인수는 아래 그림처럼 7개 영역을 만듭니다.
이항계수의 합으로 생각하면 됩니다.
$\frac{3!}{3!(0)!}+\frac{3!}{2!(1)!}+\frac{3!}{1!(2)!}=1+3+3=7$

자 이제 factorial 메소드도 필요하네요....

long long factorial(long long n)
{
    if (n == 1 || n == 0)
        return 1;
    else
        return factorial(n - 1) * n;
}

위에서 원의 각 영역을 define하기 위한 구조체도 하나 정의했습니다. level 은 몇 개가 겹치는 지를 의미합니다. 레벨1은 겹치지 않는 영역, 레벨2는 2개가 겹치는 영역 이런 식입니다. mulVal은 겹치는 영역에 해당하는 소인수를 곱한 값입니다. divVal은 n을 mulVal로 나눈 값입니다. 실질적으로 영역을 대표하는 값이라고 보면 됩니다. indices는 전체 소인수 중에 어떤 소인수를 사용하는지 표시한 vector입니다.

struct rgnT
{
    int level = -1;
    long long mulVal = 1;
    long long divVal;
    std::vector<bool> indices;
};

그리고 다음과 같이 7개 영역의 정보를 define하는 코드를 작성했습니다. 소인수가 몇 개가 될지 모르기 때문에 동적으로 작성하는 코드를 만들었습니다. 중복되지 않는 모든 조합을 찾는 것이 조금 어려웠네요.

    std::vector<std::vector<rgnT>> list;
    list.resize(sz + 1);

    long long u = factorial(sz);
    rgnT last;
    for (size_t i = 1; i <= sz; ++i)
    {
        long long b1 = factorial(i);
        long long b2 = factorial(sz - i);
        long long c = u / b1 / b2;

        std::vector<int> dd;
        for (int t = 0; t < i; ++t)
        {
            dd.push_back(t);
        }
        std::vector<std::vector<int>> itemlist;

        itemlist.push_back(dd);

        int idx = dd.size() - 1;
        while (true)
        {
            if (idx < 0)
                break;

            int cnt = itemlist.size();
            for (int t = 0; t < cnt; ++t)
            {
                std::vector<int> item = itemlist[t];
                for (int e = item.back(); e < sz; ++e)
                {
                    for (int si = idx; si < dd.size(); ++si)
                    {
                        item[si]++;
                    }
                    if (item.back() < sz)
                        itemlist.push_back(item);
                }
            }
            --idx;
        }

        for (size_t s = 0; s < itemlist.size(); ++s)
        {
            rgnT sub;
            sub.level = i;
            sub.indices.resize(sz, false);

            for (int m = 0; m < itemlist[s].size(); ++m)
            {
                sub.indices[itemlist[s][m]] = true;
                sub.mulVal *= pf[itemlist[s][m]];
            }

            sub.divVal = n / sub.mulVal;

            list[i].push_back(sub);
            last = sub;
        }
    }

여기서 주어진 것은 각각의 원의 크기입니다(n을 각각의 소인수로 나눈 값). 그런데 실제 필요한 부분은 중복되지 않은 7개 영역의 값이 필요합니다.

일단 level이 제일 높은 영역(위에서는 3개가 겹치는 중앙 영역, 레벨3)은 나머지 모든 영역에 포함이 되므로 모든 영역의 divVal을 이 영역의 divVal로 빼줍니다. 그럼 일단 모든 영역이 레벨3의 항목은 제거됩니다. 그 다음부터 조금 복잡해집니다. 레벨2에서는 원1, 원2가 겹친 영역에 해당하는 divVal을 레벨1의 원1 divVal, 원2 divVal에 빼줘야 합니다.(중복 제거) 이 작업을 레벨2까지 반복해야 합니다. 이렇게 하면 최종적으로 각 영역에 중복되지 않는 값만 존재합니다. 이 값을 모두 세어서 n에서 빼주면 정답이 됩니다.

for (int l = sz; l > 1; --l)
    {
        int rsz = list[l].size();
        for (int r = 0; r < rsz; ++r)
        {
            recus(list[l][r], list);
        }
    }

.
.
.

void recus(rgnT uRgn, std::vector<std::vector<rgnT>> &list)
{
    for (size_t l = uRgn.level - 1; l > 0; --l)
    {
        for (size_t r = 0; r < list[l].size(); ++r)
        {
            rgnT &rg = list[l][r];

            bool included = true;
            for (size_t i = 0; i < rg.indices.size(); ++i)
            {
                if (!uRgn.indices[i] && rg.indices[i])
                {
                    included = false;
                    break;
                }
            }

            if (!included)
                continue;

            rg.divVal -= uRgn.divVal;
        }
    }
}

여기까지 하면 일단 비교적 빠르게 찾을 수 있어, 테스트는 통과합니다. 하지만 이런 짓을 하자고 이런 문제를 내지는 않겠죠.

이 문제는 Euler’s totient function을 이용하면 아주 간단하게 풀 수 있는 문제였습니다.

아래는 이 수식을 이용해서 푼 예제입니다.

long long properFractions(long long n)
{
  if (n == 1) return 0;
  long long phi = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      phi = phi / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  }
  
  if (n > 1) phi = phi / n * (n - 1);
  return phi;
}

엄청 간단하죠. 이런 문제를 풀면 참 허무합니다.
오일러가 똑똑하네요...

전체 소스

https://github.com/YongheeLee/codewars_solution/blob/main/4Kyu_Number_of_Proper_Fractions_with_Denominator_d.cpp