cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/transform/multiple/divide_both.test.cpp
- View this file on GitHub
- Last update: 2022-02-25 23:20:55+09:00
- Problem: https://atcoder.jp/contests/abc206/tasks/abc206_e
Depends on
- Internal Eratosthenes
(library/number/internal_eratosthenes.hpp)
- エラトステネスの篩
(library/number/sieve_of_eratosthenes.hpp)
- 約数系ゼータ変換・メビウス変換
(library/transform/divisor.hpp)
- 倍数系ゼータ変換・メビウス変換
(library/transform/multiple.hpp)
- Default Operator
(library/util/default_operator.hpp)
Code
#define PROBLEM "https://atcoder.jp/contests/abc206/tasks/abc206_e"
#include <cassert>
#include <iostream>
#include "library/transform/multiple.hpp"
#include "library/transform/divisor.hpp"
#include "library/number/sieve_of_eratosthenes.hpp"
using namespace suisen;
const Sieve<1000000> sieve;
// count l <= x, y <= r s.t. gcd(x, y) = 1
long long count_coprime_pairs(int l, int r) {
std::vector<long long> f(r + 1, 0);
for (int g = 1; g <= r; ++g) {
long long w = r / g - (l + g - 1) / g + 1;
f[g] = w * w;
}
std::vector<long long> f_copy = f;
multiple_transform::mobius(f);
long long ret = f[1];
{
{
multiple_transform::zeta(f);
assert(f == f_copy);
multiple_transform::mobius(f);
f_copy = f;
}
std::vector<long long> div_cum_naive(r + 1, 0);
for (int g = 1; g <= r; ++g) {
for (int d : sieve.divisors(g)) {
div_cum_naive[g] += f[d];
}
}
divisor_transform::zeta(f);
assert(f == div_cum_naive);
divisor_transform::mobius(f);
assert(f == f_copy);
}
return ret;
}
int main() {
int l, r;
std::cin >> l >> r;
long long whole = (long long) (r - l + 1) * (r - l + 1);
long long coprime_pairs_num = count_coprime_pairs(l, r);
long long divisor_pairs_num = 0;
for (int g = l + (l == 1); g <= r; ++g) {
divisor_pairs_num += 2 * (r / g - 1) + 1;
}
long long ans = whole - (coprime_pairs_num + divisor_pairs_num);
std::cout << ans << std::endl;
return 0;
}#line 1 "test/src/transform/multiple/divide_both.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc206/tasks/abc206_e"
#include <cassert>
#include <iostream>
#line 1 "library/transform/multiple.hpp"
#include <vector>
#line 1 "library/util/default_operator.hpp"
namespace suisen {
namespace default_operator {
template <typename T>
auto zero() -> decltype(T { 0 }) { return T { 0 }; }
template <typename T>
auto one() -> decltype(T { 1 }) { return T { 1 }; }
template <typename T>
auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; }
template <typename T>
auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; }
template <typename T>
auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; }
template <typename T>
auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; }
template <typename T>
auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; }
template <typename T>
auto neg(const T &x) -> decltype(-x) { return -x; }
template <typename T>
auto inv(const T &x) -> decltype(one<T>() / x) { return one<T>() / x; }
} // default_operator
namespace default_operator_noref {
template <typename T>
auto zero() -> decltype(T { 0 }) { return T { 0 }; }
template <typename T>
auto one() -> decltype(T { 1 }) { return T { 1 }; }
template <typename T>
auto add(T x, T y) -> decltype(x + y) { return x + y; }
template <typename T>
auto sub(T x, T y) -> decltype(x - y) { return x - y; }
template <typename T>
auto mul(T x, T y) -> decltype(x * y) { return x * y; }
template <typename T>
auto div(T x, T y) -> decltype(x / y) { return x / y; }
template <typename T>
auto mod(T x, T y) -> decltype(x % y) { return x % y; }
template <typename T>
auto neg(T x) -> decltype(-x) { return -x; }
template <typename T>
auto inv(T x) -> decltype(one<T>() / x) { return one<T>() / x; }
} // default_operator
} // namespace suisen
#line 6 "library/transform/multiple.hpp"
namespace suisen::multiple_transform {
// Calculates `g` s.t. g(n) = Sum_{n | m} f(m) inplace.
template <typename T, auto add = default_operator::add<T>>
void zeta(std::vector<T> &f) {
const int n = f.size();
std::vector<char> is_prime(n, true);
auto cum = [&](const int p) {
const int qmax = (n - 1) / p, rmax = qmax * p;
for (int q = qmax, pq = rmax; q >= 1; --q, pq -= p) {
f[q] = add(f[q], f[pq]);
is_prime[pq] = false;
}
};
for (int p = 2; p < n; ++p) if (is_prime[p]) cum(p);
}
// Calculates `f` s.t. g(n) = Sum_{n | m} f(m) inplace.
template <typename T, auto sub = default_operator::sub<T>>
void mobius(std::vector<T> &f) {
const int n = f.size();
std::vector<char> is_prime(n, true);
auto diff = [&](const int p) {
for (int q = 1, pq = p; pq < n; ++q, pq += p) {
f[q] = sub(f[q], f[pq]);
is_prime[pq] = false;
}
};
for (int p = 2; p < n; ++p) if (is_prime[p]) diff(p);
}
} // namespace suisen::multiple_transform
#line 1 "library/transform/divisor.hpp"
#line 6 "library/transform/divisor.hpp"
namespace suisen::divisor_transform {
// Calculates `g` s.t. g(n) = Sum_{d | n} f(d) inplace.
template <typename T, auto add = default_operator::add<T>>
void zeta(std::vector<T> &f) {
const int n = f.size();
std::vector<char> is_prime(n, true);
auto cum = [&](const int p) {
for (int q = 1, pq = p; pq < n; ++q, pq += p) {
f[pq] = add(f[pq], f[q]);
is_prime[pq] = false;
}
};
for (int p = 2; p < n; ++p) if (is_prime[p]) cum(p);
}
// Calculates `f` s.t. g(n) = Sum_{d | n} f(d) inplace.
template <typename T, auto sub = default_operator::sub<T>>
void mobius(std::vector<T> &f) {
const int n = f.size();
std::vector<char> is_prime(n, true);
auto diff = [&](const int p) {
const int qmax = (n - 1) / p, rmax = qmax * p;
for (int q = qmax, pq = rmax; q >= 1; --q, pq -= p) {
f[pq] = sub(f[pq], f[q]);
is_prime[pq] = false;
}
};
for (int p = 2; p < n; ++p) if (is_prime[p]) diff(p);
}
} // namespace suisen::divisor_transform
#line 1 "library/number/sieve_of_eratosthenes.hpp"
#line 5 "library/number/sieve_of_eratosthenes.hpp"
#include <cmath>
#line 7 "library/number/sieve_of_eratosthenes.hpp"
#line 1 "library/number/internal_eratosthenes.hpp"
#include <cstdint>
#line 6 "library/number/internal_eratosthenes.hpp"
namespace suisen::internal::sieve {
constexpr std::uint8_t K = 8;
constexpr std::uint8_t PROD = 2 * 3 * 5;
constexpr std::uint8_t RM[K] = { 1, 7, 11, 13, 17, 19, 23, 29 };
constexpr std::uint8_t DR[K] = { 6, 4, 2, 4, 2, 4, 6, 2 };
constexpr std::uint8_t DF[K][K] = {
{ 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 0, 1, 1, 1, 1 },
{ 2, 2, 0, 2, 0, 2, 2, 1 }, { 3, 1, 1, 2, 1, 1, 3, 1 },
{ 3, 3, 1, 2, 1, 3, 3, 1 }, { 4, 2, 2, 2, 2, 2, 4, 1 },
{ 5, 3, 1, 4, 1, 3, 5, 1 }, { 6, 4, 2, 4, 2, 4, 6, 1 },
};
constexpr std::uint8_t DRP[K] = { 48, 32, 16, 32, 16, 32, 48, 16 };
constexpr std::uint8_t DFP[K][K] = {
{ 0, 0, 0, 0, 0, 0, 0, 8 }, { 8, 8, 8, 0, 8, 8, 8, 8 },
{ 16, 16, 0, 16, 0, 16, 16, 8 }, { 24, 8, 8, 16, 8, 8, 24, 8 },
{ 24, 24, 8, 16, 8, 24, 24, 8 }, { 32, 16, 16, 16, 16, 16, 32, 8 },
{ 40, 24, 8, 32, 8, 24, 40, 8 }, { 48, 32, 16, 32, 16, 32, 48, 8 },
};
constexpr std::uint8_t MASK[K][K] = {
{ 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 }, { 0x02, 0x20, 0x10, 0x01, 0x80, 0x08, 0x04, 0x40 },
{ 0x04, 0x10, 0x01, 0x40, 0x02, 0x80, 0x08, 0x20 }, { 0x08, 0x01, 0x40, 0x20, 0x04, 0x02, 0x80, 0x10 },
{ 0x10, 0x80, 0x02, 0x04, 0x20, 0x40, 0x01, 0x08 }, { 0x20, 0x08, 0x80, 0x02, 0x40, 0x01, 0x10, 0x04 },
{ 0x40, 0x04, 0x08, 0x80, 0x01, 0x10, 0x20, 0x02 }, { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 },
};
constexpr std::uint8_t OFFSET[K][K] = {
{ 0, 1, 2, 3, 4, 5, 6, 7, },
{ 1, 5, 4, 0, 7, 3, 2, 6, },
{ 2, 4, 0, 6, 1, 7, 3, 5, },
{ 3, 0, 6, 5, 2, 1, 7, 4, },
{ 4, 7, 1, 2, 5, 6, 0, 3, },
{ 5, 3, 7, 1, 6, 0, 4, 2, },
{ 6, 2, 3, 7, 0, 4, 5, 1, },
{ 7, 6, 5, 4, 3, 2, 1, 0, },
};
constexpr std::uint8_t mask_to_index(const std::uint8_t bits) {
switch (bits) {
case 1 << 0: return 0;
case 1 << 1: return 1;
case 1 << 2: return 2;
case 1 << 3: return 3;
case 1 << 4: return 4;
case 1 << 5: return 5;
case 1 << 6: return 6;
case 1 << 7: return 7;
default: assert(false);
}
}
} // namespace suisen::internal::sieve
#line 9 "library/number/sieve_of_eratosthenes.hpp"
namespace suisen {
template <unsigned int N>
class SimpleSieve {
private:
static constexpr unsigned int siz = N / internal::sieve::PROD + 1;
static std::uint8_t flag[siz];
public:
SimpleSieve() {
using namespace internal::sieve;
flag[0] |= 1;
unsigned int k_max = (unsigned int) std::sqrt(N + 2) / PROD;
for (unsigned int kp = 0; kp <= k_max; ++kp) {
for (std::uint8_t bits = ~flag[kp]; bits; bits &= bits - 1) {
const std::uint8_t mp = mask_to_index(bits & -bits), m = RM[mp];
unsigned int kr = kp * (PROD * kp + 2 * m) + m * m / PROD;
for (std::uint8_t mq = mp; kr < siz; kr += kp * DR[mq] + DF[mp][mq], ++mq &= 7) {
flag[kr] |= MASK[mp][mq];
}
}
}
}
std::vector<int> prime_list(unsigned int max_val = N) const {
using namespace internal::sieve;
std::vector<int> res { 2, 3, 5 };
res.reserve(max_val / 25);
for (unsigned int i = 0, offset = 0; i < siz and offset < max_val; ++i, offset += PROD) {
for (uint8_t f = ~flag[i]; f;) {
uint8_t g = f & -f;
res.push_back(offset + RM[mask_to_index(g)]);
f ^= g;
}
}
while (res.size() and (unsigned int) res.back() > max_val) res.pop_back();
return res;
}
bool is_prime(const unsigned int p) const {
using namespace internal::sieve;
switch (p) {
case 2: case 3: case 5: return true;
default:
switch (p % PROD) {
case RM[0]: return ((flag[p / PROD] >> 0) & 1) == 0;
case RM[1]: return ((flag[p / PROD] >> 1) & 1) == 0;
case RM[2]: return ((flag[p / PROD] >> 2) & 1) == 0;
case RM[3]: return ((flag[p / PROD] >> 3) & 1) == 0;
case RM[4]: return ((flag[p / PROD] >> 4) & 1) == 0;
case RM[5]: return ((flag[p / PROD] >> 5) & 1) == 0;
case RM[6]: return ((flag[p / PROD] >> 6) & 1) == 0;
case RM[7]: return ((flag[p / PROD] >> 7) & 1) == 0;
default: return false;
}
}
}
};
template <unsigned int N>
std::uint8_t SimpleSieve<N>::flag[SimpleSieve<N>::siz];
template <unsigned int N>
class Sieve {
private:
static constexpr unsigned int base_max = (N + 1) * internal::sieve::K / internal::sieve::PROD;
static unsigned int pf[base_max + internal::sieve::K];
public:
Sieve() {
using namespace internal::sieve;
pf[0] = 1;
unsigned int k_max = ((unsigned int) std::sqrt(N + 1) - 1) / PROD;
for (unsigned int kp = 0; kp <= k_max; ++kp) {
const int base_i = kp * K, base_act_i = kp * PROD;
for (int mp = 0; mp < K; ++mp) {
const int m = RM[mp], i = base_i + mp;
if (pf[i] == 0) {
unsigned int act_i = base_act_i + m;
unsigned int base_k = (kp * (PROD * kp + 2 * m) + m * m / PROD) * K;
for (std::uint8_t mq = mp; base_k <= base_max; base_k += kp * DRP[mq] + DFP[mp][mq], ++mq &= 7) {
pf[base_k + OFFSET[mp][mq]] = act_i;
}
}
}
}
}
bool is_prime(const unsigned int p) const {
using namespace internal::sieve;
switch (p) {
case 2: case 3: case 5: return true;
default:
switch (p % PROD) {
case RM[0]: return pf[p / PROD * K + 0] == 0;
case RM[1]: return pf[p / PROD * K + 1] == 0;
case RM[2]: return pf[p / PROD * K + 2] == 0;
case RM[3]: return pf[p / PROD * K + 3] == 0;
case RM[4]: return pf[p / PROD * K + 4] == 0;
case RM[5]: return pf[p / PROD * K + 5] == 0;
case RM[6]: return pf[p / PROD * K + 6] == 0;
case RM[7]: return pf[p / PROD * K + 7] == 0;
default: return false;
}
}
}
int prime_factor(const unsigned int p) const {
using namespace internal::sieve;
switch (p % PROD) {
case 0: case 2: case 4: case 6: case 8:
case 10: case 12: case 14: case 16: case 18:
case 20: case 22: case 24: case 26: case 28: return 2;
case 3: case 9: case 15: case 21: case 27: return 3;
case 5: case 25: return 5;
case RM[0]: return pf[p / PROD * K + 0] ? pf[p / PROD * K + 0] : p;
case RM[1]: return pf[p / PROD * K + 1] ? pf[p / PROD * K + 1] : p;
case RM[2]: return pf[p / PROD * K + 2] ? pf[p / PROD * K + 2] : p;
case RM[3]: return pf[p / PROD * K + 3] ? pf[p / PROD * K + 3] : p;
case RM[4]: return pf[p / PROD * K + 4] ? pf[p / PROD * K + 4] : p;
case RM[5]: return pf[p / PROD * K + 5] ? pf[p / PROD * K + 5] : p;
case RM[6]: return pf[p / PROD * K + 6] ? pf[p / PROD * K + 6] : p;
case RM[7]: return pf[p / PROD * K + 7] ? pf[p / PROD * K + 7] : p;
default: assert(false);
}
}
/**
* Returns a vector of `{ prime, index }`.
*/
std::vector<std::pair<int, int>> factorize(unsigned int n) const {
assert(0 < n and n <= N);
std::vector<std::pair<int, int>> prime_powers;
while (n > 1) {
int p = prime_factor(n), c = 0;
do { n /= p, ++c; } while (n % p == 0);
prime_powers.emplace_back(p, c);
}
return prime_powers;
}
/**
* Returns the divisors of `n`.
* It is NOT guaranteed that the returned vector is sorted.
*/
std::vector<int> divisors(unsigned int n) const {
assert(0 < n and n <= N);
std::vector<int> divs { 1 };
for (auto [prime, index] : factorize(n)) {
int sz = divs.size();
for (int i = 0; i < sz; ++i) {
int d = divs[i];
for (int j = 0; j < index; ++j) {
divs.push_back(d *= prime);
}
}
}
return divs;
}
};
template <unsigned int N>
unsigned int Sieve<N>::pf[Sieve<N>::base_max + internal::sieve::K];
} // namespace suisen
#line 9 "test/src/transform/multiple/divide_both.test.cpp"
using namespace suisen;
const Sieve<1000000> sieve;
// count l <= x, y <= r s.t. gcd(x, y) = 1
long long count_coprime_pairs(int l, int r) {
std::vector<long long> f(r + 1, 0);
for (int g = 1; g <= r; ++g) {
long long w = r / g - (l + g - 1) / g + 1;
f[g] = w * w;
}
std::vector<long long> f_copy = f;
multiple_transform::mobius(f);
long long ret = f[1];
{
{
multiple_transform::zeta(f);
assert(f == f_copy);
multiple_transform::mobius(f);
f_copy = f;
}
std::vector<long long> div_cum_naive(r + 1, 0);
for (int g = 1; g <= r; ++g) {
for (int d : sieve.divisors(g)) {
div_cum_naive[g] += f[d];
}
}
divisor_transform::zeta(f);
assert(f == div_cum_naive);
divisor_transform::mobius(f);
assert(f == f_copy);
}
return ret;
}
int main() {
int l, r;
std::cin >> l >> r;
long long whole = (long long) (r - l + 1) * (r - l + 1);
long long coprime_pairs_num = count_coprime_pairs(l, r);
long long divisor_pairs_num = 0;
for (int g = l + (l == 1); g <= r; ++g) {
divisor_pairs_num += 2 * (r / g - 1) + 1;
}
long long ans = whole - (coprime_pairs_num + divisor_pairs_num);
std::cout << ans << std::endl;
return 0;
}