test/nt/totient_of.test.cpp

• View this file on GitHub
• Last update: 2024-11-09 00:49:07+00:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D

Depends on

• bit/ctz.hpp
• nt/totient_of.hpp
• prelude.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D

#include "nt/totient_of.hpp"

int main() {
  int n; scanf("%d", &n);
  printf("%d\n", totient_of(n));
}

#line 1 "test/nt/totient_of.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D

#line 2 "prelude.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vc = vector<char>;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
auto ndvec(int n, auto e) { return vector(n, e); }
auto ndvec(int n, auto ...e) { return vector(n, ndvec(e...)); }
auto comp_key(auto&& f) { return [&](auto&& a, auto&& b) { return f(a) < f(b); }; }
auto& max(const auto& a, const auto& b) { return a < b ? b : a; }
auto& min(const auto& a, const auto& b) { return b < a ? b : a; }
#if __cpp_lib_ranges
namespace R = std::ranges;
namespace V = std::views;
#endif
#line 3 "bit/ctz.hpp"

#pragma GCC target("bmi")

template <class T>
int ctz(T x) {
  if (!x) return sizeof(T) * 8;
  if constexpr (sizeof(T) <= sizeof(unsigned)) {
    return __builtin_ctz((unsigned)x);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long long)) {
    return __builtin_ctzll((unsigned long long)x);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long long) * 2) {
    unsigned long long y = x;
    return y ? ctz(y)
             : sizeof(y) * 8 + ctz((unsigned long long)(x >> sizeof(y) * 8));
  }
}
#line 4 "nt/totient_of.hpp"

template <class T>
T totient_of(T n) {
  T res = n;
  if (n % 2 == 0) {
    res /= 2;
    n >>= ctz(n);
  }
  for (int p = 3; p * p <= n; p++) if (n % p == 0) {
    res -= res / p;
    while (n % p == 0) n /= p;
  }
  if (n != 1) res -= res / n;
  return res;
}
#line 4 "test/nt/totient_of.test.cpp"

int main() {
  int n; scanf("%d", &n);
  printf("%d\n", totient_of(n));
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-12	00_sample_00.in	AC	12 ms	8 MB
g++-12	01_small_00.in	AC	11 ms	8 MB
g++-12	01_small_01.in	AC	11 ms	8 MB
g++-12	01_small_02.in	AC	11 ms	8 MB
g++-12	01_small_03.in	AC	11 ms	8 MB
g++-12	02_medium_00.in	AC	11 ms	8 MB
g++-12	02_medium_01.in	AC	11 ms	8 MB
g++-12	02_medium_02.in	AC	11 ms	8 MB
g++-12	02_medium_03.in	AC	11 ms	8 MB
g++-12	03_large_00.in	AC	11 ms	8 MB
g++-12	03_large_01.in	AC	11 ms	8 MB
g++-12	03_large_02.in	AC	11 ms	8 MB
g++-12	03_large_03.in	AC	11 ms	8 MB
g++-12	03_large_04.in	AC	11 ms	8 MB
g++-12	03_large_05.in	AC	11 ms	8 MB
g++-12	03_large_06.in	AC	11 ms	8 MB
g++-12	03_large_07.in	AC	11 ms	8 MB
g++-12	04_maximum_00.in	AC	11 ms	8 MB
g++-12	04_maximum_01.in	AC	11 ms	8 MB
g++-12	04_maximum_02.in	AC	11 ms	8 MB
g++-12	04_maximum_03.in	AC	11 ms	8 MB
g++-12	04_maximum_04.in	AC	11 ms	8 MB
g++-12	04_maximum_05.in	AC	11 ms	8 MB

Back to top page