Subtask 1

Ta có thể giải bằng quy hoạch động với công thức : ~f[i][j]~ ~(1 \le i \le n, 1 \le j \le m)~ với ý nghĩa là số dãy con khi xét tới vị trí thứ ~i~ và trước đó ~gcd(a_1, a_2, .. a_{i - 1}) = j~.

Subtask 2

Bài toán có thể chuyển thành đếm số dãy ~n~ số nguyên tố cùng nhau, mỗi số bé hơn hoặc bằng ~\lfloor \frac{m}{k} \rfloor~.

Để giải bài toán này, ta cần biết nguyên lý bao hàm loại trừ và hàm Mobius.

Số dãy nguyên tố cùng nhau được tính bằng:

Số dãy bất kỳ
- Số dãy mà các số cùng chia hết cho 2.
- Số dãy mà các số cùng chia hết cho 3.
- Số dãy mà các số cùng chia hết cho 5.
- Số dãy mà các số cùng chia hết cho 7.
...
+ Số dãy mà các số cùng chia hết cho 2 và 3.
+ Số dãy mà các số cùng chia hết cho 2 và 5.
+ Số dãy mà các số cùng chia hết cho 2 và 7.
+ Số dãy mà các số cùng chia hết cho 3 và 5.
...
- Số dãy mà các số cùng chia hết cho 2 và 3 và 5.
...

Với số dãy chia hết cho ~x~ = ~\lfloor \frac{m}{k \times x} \rfloor ^ n~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }

const int MAXN = 1e6 + 6;
const int INF = 1e9;
const int MOD = 998244353;

int pw(int a, int n) {
    int res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        n >>= 1;
        a = a * a % MOD;
    }
    return res;
}

int n, m, k, cnt[MAXN];

void sub(int &x, int y) {
    x -= y;
    x %= MOD;
    if (x < 0) x += MOD;
}

void solve() {
    cin >> n >> m >> k;

    for (int i = 1; i <= m; i++) {
        cnt[i] = pw((m / i), n);
    }

    for (int i = m; i >= 1; --i) {
        for (int j = i + i; j <= m; j += i)
            sub(cnt[i], cnt[j]);
    }

    cout << cnt[k];
}

#define TASK ""
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}