# Project Euler

## **Problem 156**: Counting Digits
> https://projecteuler.net/problem=156
### Solution
Đầu tiên ta cần tìm cách tính $f(n, d)$

Ta sẽ tách dần dần n ra thành nhiều phần để tính
Ví dụ với $f(143, 1)$ ta sẽ tách ra $f(100, 1), f(43, 1), f(3, 1) .$

Khi đã có hàm tìm được $f(n,d)$ thì ta sẽ tìm những giá trị $n = f(n,d)$
Sau nhiều lần *bruteforce* thì ta thấy được rằng để $n = f(n,d)$ thì $n \leq 10^{12}$
Ta có thể tìm được $n$ bằng cách chặt phân
Ta liên tục chia chuỗi số thành 3 đoạn $i \rightarrow l, i \rightarrow mid, i \rightarrow r$
Từ đó ta có thể kiếm tra được $f(n,d) = n$ có tồn tại trong đoạn $i \rightarrow l$ với $i \rightarrow mid$ và $i \rightarrow mid$ với $i \rightarrow r$

#include <bits/stdc++.h>

using namespace std;

const long long MAXN = 2e7 + 10;
const long long MOD = 1e9 + 7;

long long cntNum(long long digit, long long n) {
    if (n < 10) return n < digit ? 0 : 1;

    long long shift = 1, cntAppear = 0;
    while (shift * 10 <= n) {
        shift *= 10;
        cntAppear++;
    }
    cntAppear *= shift / 10;

    long long first = n / shift;
    long long remain = n % shift;

    long long res = first * cntAppear;
    res += cntNum(digit, remain);

    if (digit == first) res += remain + 1;
    else if (digit < first && digit > 0) res += shift;

    return res;
}

long long solve(long long digit, long long l, long long r) {
    long long mid = (l + r) / 2;
    if (l == mid) {
        long long tmp = cntNum(digit, l);
        if (tmp == l) return tmp;
        return 0;
    }

    long long res = 0;
    long long cntL = cntNum(digit, l);
    long long cntR = cntNum(digit, r);
    long long cntMid = cntNum(digit, mid);
    
    if (cntMid >= l && mid >= cntL && mid > l) res += solve(digit, l, mid);
    if (cntR >= mid && r >= cntMid && r > mid) res += solve(digit, mid, r);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.tie(nullptr);

    long long res = 0;
    for (int i = 1; i <= 9; i++) {
        res += solve(i, 0, pow(10, 12));
    }
    cout << res << endl;
}

21295121502550

## **Problem 169**: Sums of Powers of Two
> https://projecteuler.net/problem=169
### Soltuion
Sau khi chạy thử 20 số đầu tiên thì ta có được dãy số

1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8

Và ta thử dãy số này trên web https://oeis.org/ thì ta thấy đây là một Stern's Diatomic Series hay còn được gọi là Fusc Function.

Ta có công thức của dãy như sau:
$a_0 = 1$; $a_1 = 1$;
$a_n$ = $\begin{cases}
a_{n/2} & n \ lẻ\\
a_{n/2} + a_{n/2-1} & n \ chẵn
\end{cases}$

Thay vì code Bignum để xử lý số lớn trong C++ ta có thể code bằng Python

dp = {0: 1, 1: 1}

def solve(n):
    if n in dp:
        return dp[n]
    if n % 2 == 0:
        dp[n] = solve(n // 2) + solve(n // 2 - 1)
        return dp[n]
    else:
        dp[n] = solve(n // 2)
        return dp[n]

    
print(solve(10 ** 25))

178653872807

## **Problem 182**: RSA Encryption
> https://projecteuler.net/problem=182
### Solution
Sau khi đọc đề thì ta thấy rằng đây là `Fixed Point in RSA encryption`

Ta thấy $m^e \equiv m \ (mod \ n)$

$\leftrightarrow$ $\begin{cases}
m^e \equiv m \ (mod \ p)\\
m^e \equiv m \ (mod \ q)
\end{cases}$ theo **Chinese Remainder Theorem**

$\rightarrow$ $m * (m^{e-1} - 1) \equiv 0 \ (mod \ p)$

$\rightarrow$ $\left[\begin{array}{l}
m \equiv 0 \ (mod \ p) \\
m^{e-1} \equiv 0 \ (mod \ (p - 1))
\end{array}\right.$

$\rightarrow$ $\left[\begin{array}{l}
m \equiv 0 \ (mod \ p) \\
(e-1) \ log(m) \equiv 0 \ (mod \ (p - 1))
\end{array}\right.$

Vậy log(m) sẽ là bội của $\frac{p-1}{gcd(e-1,p-1)}$

$\rightarrow$ Số bội sẽ là $gcd(e-1,p-1)$
$\rightarrow$ Số m hợp lệ là $gcd(e-1,p-1)+ 1$ (Tính thêm trường hợp m = 0)
Làm tương tự với q

$\rightarrow$ số lượng m sẽ là $(1+gcd(e - 1, p - 1))(1 + gcd(e - 1, p - 1))$

H t chỉ cần tìm `m` nhỏ nhất và tính tổng các số `e`

#include <bits/stdc++.h>

using namespace std;

const long long MAXN = 5;
const long long MOD = 1e8;

vector < pair <long long, long long> > res;
long long p = 1009, q = 3643, n = p * q, phi = (p - 1) * (q - 1);

long long calM(long long e) {
    long long powE = e;
    return (1 + __gcd(powE - 1, p - 1)) * (1 + __gcd(powE - 1, q - 1));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.tie(nullptr);

    for (long long i = 2; i < phi; i++) {
        if (__gcd(i, phi) == 1)
            res.emplace_back(calM(i), i);

    }
    sort(res.begin(), res.end());
    long long sol = res[0].second;
    for (int i = 1; i < res.size(); i++) {
        if (res[i].first != res[i - 1].first) {
            break;
        }
        sol += res[i].second;
    }
    cout << sol << endl;
}

399788195976

## **Problem 185**: Number Mind
> https://projecteuler.net/problem=185
### Solution
Về ý tưởng của bài này ta sẽ random 16 chữ số rồi liên tục kiểm tra kết quả
Gọi `ans` là dãy số được random ra
Gọi khoảng cách từ `ans` đến đáp án là số tổng số ký tự giống nhau của ans và dữ kiện đề bài trừ cho số chữ số đúng của dữ kiện
Vì vậy việc ta cần làm là để cho khoảng cách này tiến tới 0

Đầu tiên ta viết một hàm để tính khoảng cách:

long long cal (string s) {
    long long ans = 0, cnt = 0;
    for (int i = 1; i <= 22; i++) {
        cnt = 0;
        for (int j = 0; j < 16; j++) {
            cnt += (a[i][j] == s[j]);
        }
        ans += abs(cnt - b[i]);
    }
    return ans;
}

Tiếp theo ta sẽ random 16 chữ số

    string ans = "";
    for (int i = 1; i <= 16; i++) {
        ans += (rng() % 10) + '0';
    }

Tiếp đến ta sẽ liên tục thay thế các chữ số từ `ans` để tìm min khoảng cách cho đến khi khoảng cách bằng 0

    while (true) {
        for (int i = 1; i <= 16; i++) {
            cur = INF;
            best = '0';
            for (int j = '0'; j <= '9'; j++) {
                ans[i] = j;
                if (minimize(cur, cal(ans))) best = j;
            }
            ans[i] = best;
        }
        if (!cal(ans)) break;
    }

Tuy nhiên với cách này ta chưa chắc có thể tìm được đến kết quả hay không nên ta sẽ đột biến vài điểm trong dãy số.

        for (int rep = 1; rep <= 3; rep++) {
            int pos = rng() % 16;
            ans[pos] = (rng() % 10) + '0';
        }

Full code:

#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class X, class Y>
bool minimize(X &x, const Y &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

const long long INF = 1e18;
const long long MAXN = 1e5 + 10;

string a[MAXN];
long long b[MAXN];

long long cal (string s) {
    long long ans = 0, cnt = 0;
    for (int i = 1; i <= 22; i++) {
        cnt = 0;
        for (int j = 0; j < 16; j++) {
            cnt += (a[i][j] == s[j]);
        }
        ans += abs(cnt - b[i]);
    }
    return ans;
}

void solve() {
    string ans = "";
    for (int i = 1; i <= 16; i++) {
        ans += (rng() % 10) + '0';
    }

    long long cur, best;
    while (true) {
        for (int rep = 1; rep <= 3; rep++) {
            int pos = rng() % 16;
            ans[pos] = (rng() % 10) + '0';
        }

        for (int i = 1; i <= 16; i++) {
            cur = INF;
            best = '0';
            for (int j = '0'; j <= '9'; j++) {
                ans[i] = j;
                if (minimize(cur, cal(ans))) best = j;
            }
            ans[i] = best;
        }
        if (!cal(ans)) break;
    }

    cout << ans;

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    for (int i = 1; i <= 22; i++) {
        cin >> a[i];
        string s;
        cin >> s;
        b[i] = s[1] - '0';
        cin >> s;
    }

    solve();
    return 0;
}

4640261571849533

## **Problem 231**: Prime Factorisation of Binomial Coefficients
> https://projecteuler.net/problem=231
### Solution
Ta có công thức để tính $(C_n^k)$ là $\frac{n!}{k!*(n - k)!}$
Vậy nên ta sẽ tính tổng các thừa số nguyên tố từ n - k + 1 --> n rồi trừ cho tổng các thừa số nguyên tố từ 1 --> k
Để tăng tốc độ chạy của chương trình ta sẽ áp dụng thêm sàng nguyên tố

#include <bits/stdc++.h>
using namespace std;

const long long MAXN = 2e7 + 10;
const long long MOD = 1e9 + 7;

long long minPrime[MAXN], res;

void sieve() {
    minPrime[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        if (minPrime[i] == 0) {
            minPrime[i] = i;
            for (int j = i * 2; j < MAXN; j += i) {
                if (minPrime[j] == 0) {
                    minPrime[j] = i;
                }
            }
        }
    }
}

void factorize(bool check, long long n) {
    while (n != 1) {
        if (check) res += minPrime[n];
        else res -= minPrime[n];
        n /= minPrime[n];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cin.tie(nullptr);

    long long k = 15000000, n = 20000000;
    sieve();
    for (long long i = n - k + 1; i <= n; i++) {
        factorize(true, i);
    }
    for (long long i = 2; i <= k; i++) {
        factorize(false, i);
    }
    cout << res << endl;
}

7526965179680

## **Problem 237**: Tours on a 4 x N Playing Board
> https://projecteuler.net/problem=237
### Solution
Sau khi chạy thử 7 T(n) đầu tiên thì ta có dãy

1, 1, 4, 8, 23, 55, 144

Và ta thử dãy số này trên web https://oeis.org/ thì ta ra được công thức
$a_n = a_{n-4} - 2a_{n-3} + 2a_{n-2} + 2a_{n-1}$
Vì $10^{12}$ lớn nên thay vì chạy for bình thường ta sẽ dùng nhân ma trận

$\begin{bmatrix}
a_{n-4} & a_{n-3} & a_{n-2} & a_{n-1}
\end{bmatrix}$ * $\begin{bmatrix}
0 & 0 & 0 & 1\\
1 & 0 & 0 & -2\\
0 & 1 & 0 & 2\\
0 & 0 & 1 & 2\\
\end{bmatrix}$ = $\begin{bmatrix}
a_{n-3} & a_{n-2} & a_{n-1} & a_{n}
\end{bmatrix}$

$\begin{bmatrix}
a_{n-4} & a_{n-3} & a_{n-2} & a_{n-1}
\end{bmatrix}$ * $\begin{bmatrix}
0 & 0 & 0 & 1\\
1 & 0 & 0 & -2\\
0 & 1 & 0 & 2\\
0 & 0 & 1 & 2\\
\end{bmatrix}^{k+1}$ = $\begin{bmatrix}
a_{n-3+k} & a_{n-2+k} & a_{n-1+k} & a_{n+k}
\end{bmatrix}$

#include <bits/stdc++.h>

using namespace std;

const long long MAXN = 5;
const long long MOD = 1e8;
const long long Power = 1e12 - 4;

struct Matrix {
    long long a[MAXN][MAXN];
    Matrix() {
        memset(a, 0, sizeof(a));
    }
    Matrix operator*(const Matrix &other) const {
        Matrix res;
        for (int i = 0; i < MAXN; i++) {
            for (int j = 0; j < MAXN; j++) {
                for (int k = 0; k < MAXN; k++) {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % MOD;
                }
            }
        }
        return res;
    }

    Matrix operator^(long long n) const {
        Matrix res, base = *this;
        for (int i = 0; i < MAXN; i++) res.a[i][i] = 1;
        while (n) {
            if (n & 1) res = res * base;
            base = base * base;
            n >>= 1;
        }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.tie(nullptr);

    Matrix origin, res, base;
    origin.a[0][0] = 1; origin.a[0][1] = 1; origin.a[0][2] = 4; origin.a[0][3] = 8;

    base.a[0][0] = 0; base.a[0][1] = 0; base.a[0][2] = 0; base.a[0][3] = 1;
    base.a[1][0] = 1; base.a[1][1] = 0; base.a[1][2] = 0; base.a[1][3] = -2;
    base.a[2][0] = 0; base.a[2][1] = 1; base.a[2][2] = 0; base.a[2][3] = 2;
    base.a[3][0] = 0; base.a[3][1] = 0; base.a[3][2] = 1; base.a[3][3] = 2;

    base = base ^ Power;
    res = origin * base;
    cout << res.a[0][3] << endl;
}

15836928

## **Problem 247**: Squares Under a Hyperbola
> https://projecteuler.net/problem=247
### Solution
Với bài này ta sẽ tạo một `priority_queue` sort từ bé đến lớn theo độ dài cạnh hình vuông để đánh index
Ta giả dụ nếu hình vuông có toạ độ góc trái dưới là $(x_0, y_0)$ và toạ độ góc phải trên là $(x_1, y_1)$ thì ta sẽ có cạnh hình vuông là $x_1 - x_0 = y_1 - y_0$
$\leftrightarrow$ $x_1 - x_0 = \frac{1}{x_0} - y_0$
$\leftrightarrow$ $\frac{x_1^2-1}{x_1} = x_0 - y_0$
$\leftrightarrow$ $x_1^2 - x_1(x_0 - y_0) - 1 = 0$
$\leftrightarrow$ $x_1 = -\frac{y_0 - x_0}{2} + \sqrt{(\frac{y_0 - x_0}{2})^2 + 1}$
$\leftrightarrow$ $x_1 = \frac{x_0 - y_0 + \sqrt{(x_0 - y_0)^2 + 4}}{2}$
Vậy nên cạnh = $x_1 - x_0 = \frac{x_0 - y_0 + \sqrt{(x_0 - y_0)^2 + 4}}{2} - x_0 = \frac{-x_0 - y_0 + \sqrt{(x_0 - y_0)^2 + 4}}{2}$

Gọi biến check là số hình vuông thoã mãn điều kiện
Ta sẽ liên tục tăng res lên cho đến khi check = 0
Với mỗi vòng lặp ta sẽ push vô queue hai hình vuông nằm phía bên phải và bên trên
Từ đó ta có thể biết được số lượng hình vuông bên dưới và bên trái của mỗi hình vuông khi check

#include <bits/stdc++.h>

using namespace std;

const long long MAXN = 2e7 + 10;
const long long MOD = 1e9 + 7;

struct Square {
    double x, y;
    long long left, bottom;

    Square(double _x, double _y, long long _left, long long _bottom) {
        x = _x;
        y = _y;
        left = _left;
        bottom = _bottom;
    }

    double lenSquare;

    bool operator<(const Square &other) const {
        return lenSquare < other.lenSquare;
    }

    void setLen() {
        lenSquare = 0.5 * (sqrt((x - y) * (x - y) + 4) - x - y);
    }
};

long long iL = 0, iB = 1, res, check = 1;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.tie(nullptr);

    priority_queue <Square> squares;
    squares.emplace(1, 0, 0, 0);

    while (check > 0) {
        res++;

        Square cur = squares.top();
        squares.pop();

        cur.setLen();
        Square top = Square(cur.x, cur.y + cur.lenSquare, cur.left, cur.bottom + 1);
        top.setLen();
        squares.push(top);
        Square right = Square(cur.x + cur.lenSquare, cur.y, cur.left + 1, cur.bottom);
        right.setLen();
        squares.push(right);

        if (top.left <= iL && top.bottom <= iB) check++;
        if (right.left <= iL && right.bottom <= iB) check++;
        if (cur.left <= iL && cur.bottom <= iB) check--;
    }
    cout << res << endl;
}

782252