# Training Contest 2

## A. [GCC TRAINING 2025 - PRACTICE 2] Số chính giữa

#include <bits/stdc+.h>

using namespace std;

#define ll long long

int main() 
{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    ll x, y;
    if (!(cin >> x >> y)) return 0;
    cout << std::gcd(x, y);
    return 0;
}

## B. [GCC TRAINING 2025 - PRACTICE 2] Phân tích thừa số nguyên tố

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() 
{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    ll N;
    if (!(cin >> N)) return 0;

    vector<pair<ll>> fac;
    for (ll p = 2; p * p <= N; ++p) {
        if (N % p == 0) {
            int e = 0;
            while (N % p == 0) { N /= p; ++e; }
            fac.push_back({p, e});
        }
    }
    if (N > 1) fac.push_back({N, 1});

    for (size_t i = 0; i < fac.size(); ++i) {
        cout << fac[i].first << "^" << fac[i].second;
        if (i + 1 < fac.size()) cout << " x ";
    }
    return 0;
}

## C. [GCC TRAINING 2025 - PRACTICE 2] Ước số

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() 
{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    ll N;
    if (!(cin >> N)) return 0;

    ll ans = 1;
    for (ll p = 2; p * p <= N; ++p) {
        if (N % p == 0) {
            int e = 0;
            while (N % p == 0) { N /= p; ++e; }
            ans *= (e + 1);
        }
    }
    if (N > 1) ans *= 2;
    cout << ans;
    return 0;
}

## D. [GCC TRAINING 2025 - PRACTICE 2] Số mạnh mẽ

## E. [GCC TRAINING 2025 - PRACTICE 2] Số vui vẻ

## G. [GCC TRAINING 2025 - PRACTICE 2] Số đặc biệt

## H. [GCC TRAINING 2025 - PRACTICE 2] Số SIÊU nguyên tố

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

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

    int N; 
    if (!(cin >> N)) return 0;

    vector<bool> prime(N + 1, true);
    if (N >= 0) prime[0] = false;
    if (N >= 1) prime[1] = false;
    for (int p = 2; p * p <= N; ++p)
        if (prime[p])
            for (int q = p * p; q <= N; q += p) prime[q] = false;

    auto isSuperPrime = [&](int x) {
        while (x > 0) {
            if (x > N ? false : !prime[x]) return false
            x /= 10;
        }
        return true;
    };

    vector<int> ans;
    for (int i = 2; i <= N; ++i)
        if (isSuperPrime(i)) ans.push_back(i);

    if (ans.empty()) { cout << -1; }
    else {
        for (size_t i = 0; i < ans.size(); ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
    }
    return 0;
}

## I. [GCC TRAINING 2025 - PRACTICE 2] Bảng cửu chương

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

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

    int T; 
    if (!(cin >> T)) return 0;
    for (int tc = 0; tc < T; ++tc) {
        long long n; 
        cin >> n;
        for (int i = 1; i <= 10; ++i) {
            cout << n << " x " << i << " = " << n * i << '\n';
        }
    }
    return 0;
}

## J. [GCC TRAINING 2025 - PRACTICE 2] Vẽ hình

N = int(input())

# top
for i in range(1, N):
    if i == 1: print("*")
    elif i == 2: print("**")
    else: print("*" + " "*(i-2) + "*")

# middle
print("*"*(2*N-1))

# bottom
for j in range(1, N):
    lead = " "*(N + j - 1)
    if j == N-1:
        print(lead + "*")
    else:
        inner = N - j - 2
        print(lead + ("**" if inner == 0 else "*" + " "*inner + "*"))

## K. [GCC TRAINING 2025 - PRACTICE 2] In đơn giản

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

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

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; cin >> n;
        for (int i = n - 1; i >= 0; --i) {
            cout << i;
            if (i) cout << ' ';
        }
        cout << '\n';
    }
    return 0;
}

## L. [GCC TRAINING 2025 - PRACTICE 2] Chữ số cuối cùng khác 0

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

int pow2mod10(long long e) {
    if (e == 0) return 1;
    int cyc[5] = {0, 2, 4, 8, 6};
    int r = e % 4;
    return (r == 0) ? 6 : cyc[r];
}

int lastNonZero(long long n) {
    static int base[5] = {1, 1, 2, 6, 4};
    if (n < 5) return base[n];
    return ( lastNonZero(n / 5) * base[n % 5] * pow2mod10(n / 5) ) % 10;
}

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

    long long n;
    if (!(cin >> n)) return 0;
    cout << lastNonZero(n) << "\n";
    return 0;
}

## M. [GCC TRAINING 2025 - PRACTICE 2] Phép toán cơ bản

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

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

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; cin >> n;

        vector<int> P;
        for (int i = n - 1; i >= 1; --i) P.push_back(i);
        P.push_back(0);
        for (int i = 1; i <= n - 1; ++i) P.push_back(i);

        auto print_with_m = [&](int m){
            for (int x : P) {
                int v = min(x, m);
                cout << char('a' + v);
            }
            cout << '\n';
        };

        for (int m = n - 1; m >= 1; --m) print_with_m(m);
        print_with_m(0);
        for (int m = 1; m <= n - 1; ++m) print_with_m(m);
    }
    return 0;
}

## N. [GCC TRAINING 2025 - PRACTICE 2] Trò chơi nối điểm

T = int(input())
for _ in range(T):
    n = int(input())
    print("Susan" if n % 4 in (2, 3) else "Alice")

## O. [GCC TRAINING 2025 - PRACTICE 2] Tổng cấp số nhân

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1'000'000'007LL;

long long modpow(long long a, long long e){
    long long r = 1 % MOD;
    a %= MOD;
    while (e){
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

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

    long long A, N;
    if (!(cin >> A >> N)) return 0;

    if (A == 1) {
        cout << (N + 1) % MOD << '\n';
    } else {
        long long num = (modpow(A, N + 1) - 1 + MOD) % MOD;
        long long den_inv = modpow(A - 1, MOD - 2);
        cout << (num * den_inv) % MOD << '\n';
    }
    return 0;
}

## P. [GCC TRAINING 2025 - PRACTICE 2] Vẽ hình thoi

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

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

    int n; 
    if (!(cin >> n)) return 0;

    int cur = 1;

    for (int i = 1; i <= n; ++i) {
        cout << string(n - i, ' ');
        for (int j = 0; j < i; ++j) cout << cur++ << ' ';
        cout << '\n';
    }
    for (int i = n - 1; i >= 1; --i) {
        cout << string(n - i, ' ');
        for (int j = 0; j < i; ++j) cout << cur++ << ' ';
        cout << '\n';
    }
    return 0;
}

## Q. [GCC TRAINING 2025 - PRACTICE 2] Kiểm tra số nguyên tố

## R. [GCC TRAINING 2025 - PRACTICE 2] Ăn kẹo

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

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

    long long n, k;
    if (!(cin >> n >> k)) return 0;
    cout << (n + k - 1) / k << '\n';
    return 0;
}

## S. [GCC TRAINING 2025 - PRACTICE 2] Mảng hoàn hảo


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

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

    int N; 
    if (!(cin >> N)) return 0;

    vector<bool> seen(N + 1, false);
    long long sum = 0;
    int unique_cnt = 0;
    bool ok = true;

    for (int i = 0; i < N; ++i) {
        int x; cin >> x;
        sum += x;
        if (1 <= x && x <= N && !seen[x]) {
            seen[x] = true;
            ++unique_cnt;
        } else {
            ok = false;
        }
    }

    if (ok && unique_cnt == N) {
        cout << "YES " << sum << "\n";
    } else {
        cout << "NO\n";
    }
    return 0;
}

## T. [GCC TRAINING 2025 - PRACTICE 2] Soul Society

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

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

    int n; 
    if (!(cin >> n)) return 0;
    vector<int> present(101, 0);

    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        if (0 <= x && x <= 100) present[x] = 1;
    }

    for (int v = 0; v < 100; ++v) {
        if (present[v] && present[v + 1]) {
            cout << 2 << '\n';
            return 0;
        }
    }
    cout << 1 << '\n';
    return 0;
}

## U. [GCC TRAINING 2025 - PRACTICE 2] Soul Society 2

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

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

    int n; 
    if (!(cin >> n)) return 0;

    const int MAXA = 100000;
    vector<long long> cnt(MAXA + 1, 0);
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        ++cnt[x];
    }

    long long ans = 0;
    for (long long f : cnt) if (f >= 2) ans += f * (f - 1) / 2;
    cout << ans << '\n';
    return 0;
}

## V. [GCC TRAINING 2025 - PRACTICE 2] Xếp sách

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

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

    vector<int> a;
    int x;
    while (cin >> x) a.push_back(x);riêng)

    int n = (int)a.size();
    int need = n;
    for (int i = n - 1; i >= 0; --i) {
        if (a[i] == need) --need;
    }
    cout << need << '\n';
    return 0;
}

## W. [GCC TRAINING 2025 - PRACTICE 2] Dãy con E2

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

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

    int N; 
    if (!(cin >> N)) return 0;
    vector<long long> a(N);
    long long mx = 0;
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    int best = 0, cur = 0;
    for (int i = 0; i < N; ++i) {
        if (a[i] == mx) {
            ++cur;
            best = max(best, cur);
        } else cur = 0;
    }

    cout << best << '\n';
    return 0;
}