Initial commit

6 files changed, 143 insertions, 0 deletions

diff --git a/07_mathematics/a.out b/07_mathematics/a.out
new file mode 100755
index 0000000..d03560d
--- /dev/null
+++ b/07_mathematics/a.out
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 <array>
+#include <bitset>
+#include <iostream>
+
+// 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<size_t, max> spf; // Smallest prime factor of i
+std::array<size_t, max> 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 <array>
+#include <iostream>
+
+constexpr size_t max = 1000001;
+std::array<size_t, max> 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 <iostream>
+
+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 <iostream>
+
+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 <iostream>
+
+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";
+        }
+}