math/alternative-totient.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "math/alternative-totient.hpp"

Depends on

• math/base.hpp
• math/factorize.hpp

Code

#pragma once

#include "./base.hpp"
#include "./factorize.hpp"

#include <algorithm>
#include <vector>

namespace matumoto {
  long long alternative_totient(long long x, long long n) {
    if (x == 1)
      return n;
    auto ps = factorize(x);
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    int k = ps.size();
    long long res = n - x;
    for (int i = 1; i < (1 << k); i++) {
      long long prod = 1;
      int cnt = 0;
      for (int j = 0; j < k; j++) {
        if (i >> j & 1) {
          prod *= ps[j];
          cnt++;
        }
      }
      if (cnt % 2) {
        res += (n - x) / prod;
      } else {
        res -= (n - x) / prod;
      }
    }
    return res;
  }
} // namespace matumoto

#line 2 "math/alternative-totient.hpp"

#line 2 "math/base.hpp"

namespace matumoto {
  using namespace std;
  using ll = long long;
} // namespace matumoto
#line 2 "math/factorize.hpp"

#include <vector>

namespace matumoto {
  vector<ll> factorize(ll n) {
    vector<ll> res;
    for (ll i = 2; i * i <= n; i++) {
      while (n % i == 0) {
        res.emplace_back(i);
        n /= i;
      }
    }
    if (n > 1)
      res.emplace_back(n);
    return res;
  }
} // namespace matumoto
#line 5 "math/alternative-totient.hpp"

#include <algorithm>
#line 8 "math/alternative-totient.hpp"

namespace matumoto {
  long long alternative_totient(long long x, long long n) {
    if (x == 1)
      return n;
    auto ps = factorize(x);
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    int k = ps.size();
    long long res = n - x;
    for (int i = 1; i < (1 << k); i++) {
      long long prod = 1;
      int cnt = 0;
      for (int j = 0; j < k; j++) {
        if (i >> j & 1) {
          prod *= ps[j];
          cnt++;
        }
      }
      if (cnt % 2) {
        res += (n - x) / prod;
      } else {
        res -= (n - x) / prod;
      }
    }
    return res;
  }
} // namespace matumoto

Back to top page