Number of Proper Fractions with Denominator d (4kyu)

https://www.codewars.com/kata/55b7bb74a0256d4467000070/cpp
解く前に気分が悪い問題
一般的にこの問題には公式がある.
3日間かかったが、他の答えから見ると、公式の問題がある.より小さなコードでより速くなります.もちろんです.
問題は次のとおりです.
大きな数(long longタイプ)nがあり、より小さな数(1,...,n−1)を分母とし、nを分子とする場合、この分数をカウントすることはできない.
n=6 n=6 n=6なら16,56frac{1}{6},frac{5}{6}61,65しかないので正解は2である.残りは、26=13、36=12、46=23frac{2}{3}=frac{1}{3}、frac{4}{6}=frac{2}62=31、63=21、64=32に分けることができるため、除外される可能性があります.
まず私の方法は
分割条件を考慮すると,同じ小さな因子(Prime Factor)を持つものと見なし,nより小さい数からnを持たない小さな因子を減算した.たとえば、6の場合、小数は2,3です.上記の場合、2、3、4はいずれも素数として2または3を有する.
基本的な方法は、これらの部分を排除することです.
このため、まず小数点以下を分解する方法を作成しました.
2から始まる引数dは、残りの変数が0の場合、更新を継続する.
速度を速めるために、tという変数をdに分けると、nも一緒に分けられ、徐々にサイズが小さくなります.
また、終了条件は、dがsqrt(t)より大きいことも許されない.3×5,4×43\times 5, 4\times 43×5,4×4,5といえば×35\times 35×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未満の数を求めた素数に分割できるかどうかを決定する必要がある.
1からn−1までのすべての数について、nの素数で除算することができ、除算しなければよい.でもこの問題nはlong longタイプかもしれないので時間がかかります
だから私が考えている方法はn個の素数に分けることができる数を見つけることです.たとえば、20の素数は2と5です.2に分けられる数は、20/2=1020/2=1020/2=10、20/5=420/5=420/5=420/5=420/5=4です.では14個あり、答えは208714=620-14=6208714=6で、これでいいのですが、重複要因もあります.10と20です繰り返しを考えると、答えは8です.この方法では、プロセス全体をループする必要はありません.そのため、速度は速いですが、冗長要素を処理する必要があります.次のアルゴリズムを考えましたますます山の上へ行ってしまったこの時からやり損なったと思ったけど最後まで行くことにした工事は彼を帰らせる基本だからだ.
次の図は、3つの円の繰り返しを示しています.
この問題には3つの小さな因数がある.
次の図に示すように、3つの引数で7つの領域を作成します.
この係数の和と見なす.
3!3!(0)!+3!2!(1)!+3!1!(2)!=1+3+3=7\frac{3!}{3!(0)!}+\frac{3!}{2!(1)!}+\frac{3!}{1!(2)!}=1+3+3=73!(0)!3!​+2!(1)!3!​+1!(2)!3!​=1+3+3=7

まだ階乗方法が必要です...

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

円の各領域を定義する構造体も定義されています.levelは、重複がいくつあるかを示します.レベル1は重複しない領域であり、レベル2は2つの重複する領域である.mulValは、上書き領域の小数に乗じた値です.divValは、nをmulValで割った値です.これは実際には領域を表す値です.インデックスは、引数全体で使用される引数を表すベクトルです.

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

次に、次のコードを作成して、7つの領域の情報を定義します.小数がいくつあるか分からないので、動的に書かれたコードを作成しました.重複しないすべての組み合わせを見つけるのは少し難しいです.

    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関数を用いて簡単に解決できる問題である.
次に、この式を使用して解く例を示します.

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