verify-check/AOJ-NTL-1-D.test.cpp

• View this file on GitHub
• Last update: 2023-09-17 19:02:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_D

Depends on

• オイラーのφ関数（C++） (num_theory/Eulers_totient_function.cpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_D"
#include <iostream>
#include "num_theory/Eulers_totient_function.cpp"
using namespace std;
int main() {
    int N;
    cin >> N;
    cout << Eulers_Totient_Function(N) << endl;
    return 0;
}

#line 1 "verify-check/AOJ-NTL-1-D.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_D"
#include <iostream>
#line 1 "num_theory/Eulers_totient_function.cpp"
int Eulers_Totient_Function(int N) {
    // 初期値
    int result = N;

    // 素因数分解用の数字
    int num = 2;

    // numがNの平方根以下になるまで繰り返し
    while (num * num <= N) {
        // numがresultの因数の場合はφ関数に操作を行う
        if (N % num == 0) {
            result = (result / num) * (num - 1);

            // numを因数に含んでいる限り操作を行い、Nに含まれる因数numをなくしている
            while (N % num == 0) {
                N /= num;
            }
        }

        // numを変更して次の素因数を探す
        num++;
    }

    // まだ素因数が残っている場合、φ関数を操作する
    if (N > 1) {
        result = (result / N) * (N - 1);
    }

    return result;
}
#line 4 "verify-check/AOJ-NTL-1-D.test.cpp"
using namespace std;
int main() {
    int N;
    cin >> N;
    cout << Eulers_Totient_Function(N) << endl;
    return 0;
}

Back to top page