From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 07_mathematics/a.out | Bin 0 -> 48984 bytes 07_mathematics/common_divisors_1081.cpp | 53 ++++++++++++++++++++++++++++++ 07_mathematics/counting_divisors_1713.cpp | 34 +++++++++++++++++++ 07_mathematics/exponentiation_1095.cpp | 19 +++++++++++ 07_mathematics/exponentiation_ii_1712.cpp | 20 +++++++++++ 07_mathematics/josephus_queries_2164.cpp | 17 ++++++++++ 6 files changed, 143 insertions(+) create mode 100755 07_mathematics/a.out create mode 100644 07_mathematics/common_divisors_1081.cpp create mode 100644 07_mathematics/counting_divisors_1713.cpp create mode 100644 07_mathematics/exponentiation_1095.cpp create mode 100644 07_mathematics/exponentiation_ii_1712.cpp create mode 100644 07_mathematics/josephus_queries_2164.cpp (limited to '07_mathematics') diff --git a/07_mathematics/a.out b/07_mathematics/a.out new file mode 100755 index 0000000..d03560d Binary files /dev/null and b/07_mathematics/a.out differ diff --git a/07_mathematics/common_divisors_1081.cpp b/07_mathematics/common_divisors_1081.cpp new file mode 100644 index 0000000..497ce4b --- /dev/null +++ b/07_mathematics/common_divisors_1081.cpp @@ -0,0 +1,53 @@ +#include +#include +#include + +// This method is very different (and more complicated) than the one used +// in the official solution. +// First we save in spf[i] the smallest prime number that divides i. +// Then we initialize an array d with d[i] being 1 if i is in the input. +// Then we loop backwards and we search all divisors of the numbers marked +// in d. For each number we encounter, we look at its maximal divisors. +// If any of them was already found, we update our candidate solution. +// To avoid looking at a divisor more than once, we save in d[i] the +// smallest prime we want to continue diving i by to find more divisors. + +constexpr size_t max = 1000001; +std::array spf; // Smallest prime factor of i +std::array d; + +int main() { + for (size_t i = 2; i < max; i++) { + if (spf[i] != 0) continue; + spf[i] = i; + for (size_t j = 2; i*j < max; j++) + if (spf[i*j] == 0) + spf[i*j] = i; + } + + size_t n, sol{1}; + std::cin >> n; + for (size_t i = 0; i < n; i++) { + size_t x; + std::cin >> x; + if (d[x] != 0) sol = std::max(sol, x); + d[x] = 1; + } + + for (size_t i = max-1; i >= sol; i--) { + if (d[i] == 0) continue; + + // Loop over maximal divisors of i + size_t y{i}; + while (y != 1) { + size_t p = spf[y]; + if (i/p < sol) break; + if (p >= d[i]) { + if (d[i/p] != 0) sol = std::max(sol, i/p); + d[i/p] = p; + } + while (y % p == 0) y /= p; + } + } + std::cout << sol << "\n"; +} diff --git a/07_mathematics/counting_divisors_1713.cpp b/07_mathematics/counting_divisors_1713.cpp new file mode 100644 index 0000000..fe30ab4 --- /dev/null +++ b/07_mathematics/counting_divisors_1713.cpp @@ -0,0 +1,34 @@ +#include +#include + +constexpr size_t max = 1000001; +std::array spf; // Smallest prime factor of i + +size_t ndiv(size_t x) { + size_t n{1}, d{0}, e{0}; + for (size_t i = x; i > 1; i /= spf[i]) { + if (spf[i] != d) { + n *= e+1; + d = spf[i]; + e = 1; + } else e++; + } + return n * (e+1); +} + +int main() { + for (size_t i = 2; i < max; i++) { + if (spf[i] != 0) continue; + spf[i] = i; + for (size_t j = 2; i*j < max; j++) + if (spf[i*j] == 0) + spf[i*j] = i; + } + + size_t n, x; + std::cin >> n; + for (size_t i = 0; i < n; i++) { + std::cin >> x; + std::cout << ndiv(x) << "\n"; + } +} diff --git a/07_mathematics/exponentiation_1095.cpp b/07_mathematics/exponentiation_1095.cpp new file mode 100644 index 0000000..1ba8509 --- /dev/null +++ b/07_mathematics/exponentiation_1095.cpp @@ -0,0 +1,19 @@ +#include + +static constexpr unsigned long long MOD = 1000000007; + +unsigned long long pow(unsigned long long a, unsigned long long b) { + if (b == 0) return 1; + if (a == 0) return 0; + if (b % 2 == 0) return pow(a*a % MOD, b/2) % MOD; + return (a * pow(a, b-1)) % MOD; +} + +int main() { + unsigned long long n, a, b; + std::cin >> n; + for (unsigned long long i = 0; i < n; i++) { + std::cin >> a >> b; + std::cout << pow(a, b) << "\n"; + } +} diff --git a/07_mathematics/exponentiation_ii_1712.cpp b/07_mathematics/exponentiation_ii_1712.cpp new file mode 100644 index 0000000..6a894f5 --- /dev/null +++ b/07_mathematics/exponentiation_ii_1712.cpp @@ -0,0 +1,20 @@ +#include + +static constexpr unsigned long long MOD = 1000000007; + +unsigned long long pow(unsigned long long a, unsigned long long b, + unsigned long long mod) { + if (b == 0) return 1; + if (a == 0) return 0; + if (b % 2 == 0) return pow(a*a % mod, b/2, mod) % mod; + return (a * pow(a, b-1, mod)) % mod; +} + +int main() { + unsigned long long n, a, b, c; + std::cin >> n; + for (unsigned long long i = 0; i < n; i++) { + std::cin >> a >> b >> c; + std::cout << pow(a, pow(b, c, MOD-1), MOD) << "\n"; + } +} diff --git a/07_mathematics/josephus_queries_2164.cpp b/07_mathematics/josephus_queries_2164.cpp new file mode 100644 index 0000000..b17f3c9 --- /dev/null +++ b/07_mathematics/josephus_queries_2164.cpp @@ -0,0 +1,17 @@ +#include + +int f(int n, int k, int m) { + int h = n/2 + m*(n%2); + if (n == 1) return 1; + if (k <= h) return 2*k-m; + return 2*f(n-h, k-h, m^(n%2))+m-1; +} + +int main() { + int q, n, k; + std::cin >> q; + for (int i = 0; i < q; i++) { + std::cin >> n >> k; + std::cout << f(n, k, 0) << "\n"; + } +} -- cgit v1.3