Kiểu dữ liệu long long sẽ không lưu được số Fibonacci thứ $$$92$$$. Như vậy, chúng ta sẽ phải dùng unsigned long long.

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

#define el '\n'
#define int unsigned long long

int f[100];

void solve(){
    int n; cin >> n;
    cout << f[n] << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    f[0] = f[1] = 1;
    for(int i=2; i<=92; i++) f[i] = f[i - 1] + f[i - 2];

    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Với giới hạn lên tới $$$10^6$$$, việc duyệt qua từng số rồi tìm ước nguyên tố lớn nhất là không thể, vì ta sẽ mất $$$O(\sqrt n)$$$ để tìm ước, tức là xấp xỉ $$$10^3$$$ $$$\to$$$ tổng độ phức tạp sẽ là $$$O(10^9)$$$, vượt quá $$$1$$$ giây cho phép.

• Để có thể tối ưu được thời gian, ta sẽ cần sử dụng Sàng Biến Đổi ở đây. Đầu tiên, ta sẽ duyệt qua các số trong đoạn $$$[2, 10^6]$$$, với mỗi số $$$i$$$ đang xét tới, ta sẽ duyệt các bội của nó và cập nhật ước nguyên tố lớn nhất hiện tại chính là $$$i$$$. Tiếp theo, các truy vấn tính tổng tĩnh trong đoạn $$$[l, r]$$$ nào đó, ta sẽ phải nghĩ ngay đến Tổng cộng dồn để tiếp tục tối ưu thời gian, chứ không thể duyệt trâu các truy vấn được.

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

#define el '\n'
 
int d[1000005];
long long f[1000005];
void pre(){
    for(int i=2; i<=1e6; i++){
        if(d[i] == 0){
            for(int j=i; j<=1e6; j+=i){
                d[j] = i;
            }
        }
    }
    for(int i=2; i<=1e6; i++){
        f[i] = f[i - 1] + d[i];
    }
}
 
void solve(){
    int l, r; cin >> l >> r;
    cout << f[r] - f[l - 1] << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;



void LonggVuz(){
    int n, q; cin >> n >> q;
    int a[n+5] = {};
    while(q--){
        int l, r; cin >> l >> r;
        ++a[l]; --a[r + 1];
    }
    fo(i, 1, n){
        a[i] += a[i - 1];
        cout << a[i] % 2 << ' ';
    }
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

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

#define el '\n'
#define mod 1000000007
#define mxn 1000006

int n, dp[mxn];
 
void solve(){
    cin >> n;
    dp[0] = 1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=6; j++){
            if(i >= j){
                dp[i] = (dp[i] + dp[i - j]) % mod;
            }
        }
    }
    cout << dp[n];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Ta sẽ sử dụng quy hoạch động để giải quyết bài toán này, gần giống bài tìm dãy con tăng dài nhất nhưng thay số bằng ký tự. Gọi $$$dp_i$$$ là dãy con không giảm dài nhất kết thúc tại vị trí $$$i$$$.

• Cơ sở quy hoạch động sẽ là mọi dãy con độ dài $$$1$$$ đều thoả mãn, sau đó ta sẽ duyệt qua từng phần tử $$$j$$$ phía trước phần tử $$$i$$$ đang xét, nếu $$$a_j \le a_i$$$ thì ta sẽ cập nhật $$$dp_i = max(dp_i, dp_j + 1)$$$. Đáp số của bài toán sẽ là $$$max(dp_1, dp_2, ..., dp_n)$$$.

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

#define el '\n'

int dp[5005];
void solve(){
    int n; cin >> n;
    string a; cin >> a;
    a = "@" + a;
    int res = 1;
    for(int i=1; i<=n; i++){
        dp[i] = 1;
        for(int j=1; j<i; j++){
            if(a[i] >= a[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 5005

bool dx[mxn][mxn];
 
void solve(){
    string a; cin >> a;
    int n = a.size();
    a = "@" + a;
    for(int i=1; i<=n; i++) dx[i][i] = 1;
    for(int len=2; len<=n; len++){
        for(int i=1; i<=n-len+1; i++){
            int j = i + len - 1;
            if(a[i] == a[j]){
                if(len == 2) dx[i][j] = 1;
                else dx[i][j] = dx[i + 1][j - 1];
            }
        }
    }
    int q; cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        if(dx[l][r]) cout << "Yes\n";
        else cout << "No\n";
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, dp[1005][1005];
char a[1005][1005];

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> a[i][j];
        }
    }
    if(a[1][1] == '*') out(0);
    dp[1][1] = 1;
    for(int i=2; i<=n; i++){
        if(a[1][i] == '*') break;
        dp[1][i] = dp[1][i - 1];
    }
    for(int i=2; i<=n; i++){
        if(a[i][1] == '*') break;
        dp[i][1] = dp[i - 1][1];
    }
    for(int i=2; i<=n; i++){
        for(int j=2; j<=n; j++){
            if(a[i][j] == '.'){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                dp[i][j] %= mod;
            }
        }
    }
    cout << dp[n][n];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define ms(a, x) memset(a, x, sizeof(a))
#define all(x) begin(x), end(x)
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e4 + 7;

int dp[mxn];
// dp[i] : giá trị lớn nhất đạt được khi cái túi có khối lượng là i

signed main(){
    cin.tie(NULL) -> sync_with_stdio(false);

    int n, m; cin >> n >> m;
    int w[n+5], v[n+5];
    for(int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
    }
    for(int i=1; i<=n; i++){
        for(int j=m; j>=w[i]; j--){
            if(j - w[i] == 0 or dp[j - w[i]] > 0){
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
    }
    int res = -1;
    for(int i=1; i<=m; i++){
        res = max(res, dp[i]);
    }
    cout << res;
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, a[5005], dp[5005], tv[5005];

void solve(){
    cin >> n;
    dp[0] = 1;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    int mx = 1, id = 0;
    for(int i=1; i<=n; i++){
        dp[i] = 1;
        tv[i] = 0;
        for(int j=1; j<i; j++){
            if(a[i] > a[j]){
                if(dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    tv[i] = j;
                }
            }
        }
        if(dp[i] > mx){
            mx = dp[i];
            id = i;
        }
    }
    cout << mx << el;
    vector<int> v;
    while(id > 0){
        v.push_back(a[id]);
        id = tv[id];
    }
    reverse(all(v));
    for(int &i : v) cout << i << ' ';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

string a, b;
int n, m, dp[5005][5005];
 
void solve(){
    cin >> a >> b;
    n = a.size();
    m = b.size();
    a = " " + a; 
    b = " " + b;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
        }
    }
    string s = "";
    while(n and m){
        if(a[n] == b[m]){
            s += a[n];
            --n; --m;
        }else{
            if(dp[n - 1][m] > dp[n][m - 1]) --n;
            else --m;
        }
    }
    reverse(s.begin(), s.end());
    cout << s;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005

int f[mxn][5];
 
void solve(){
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        int a, b, c; cin >> a >> b >> c;
        f[i][1] = max(f[i-1][2], f[i-1][3]) + a;
        f[i][2] = max(f[i-1][1], f[i-1][3]) + b;
        f[i][3] = max(f[i-1][1], f[i-1][2]) + c;
    }
    cout << max({f[n][1], f[n][2], f[n][3]});
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 100005

int f[mxn][5];
 
void solve(){
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        int a, b, c; cin >> a >> b >> c;
        f[i][1] = max(f[i-1][2], f[i-1][3]) + a;
        f[i][2] = max(f[i-1][1], f[i-1][3]) + b;
        f[i][3] = max(f[i-1][1], f[i-1][2]) + c;
    }
    cout << max({f[n][1], f[n][2], f[n][3]});
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 100005
#define int long long

int n, a[mxn], dp[mxn][2];
 
void solve(){
    cin >> n;
    for(int i=1; i<n; i++) cin >> a[i];
    dp[1][0] = 1e16;
    dp[1][1] = a[1];
    for(int i=2; i<n; i++){
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i];
    }
    cout << dp[n - 1][1];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 3003

string a;
int q, dp[mxn][mxn];
bool dx[mxn][mxn];
 
void solve(){
    cin >> a >> q;
    int n = a.size();
    a = " " + a;
    for(int i=1; i<=n; i++){
        dx[i][i] = 1;
        dp[i][i] = 1;
    }
    for(int len=2; len<=n; len++){
        for(int i=1; i<=n-len+1; i++){
            int j = i + len - 1;
            if(a[i] == a[j]){
                if(len == 2) dx[i][j] = 1;
                else dx[i][j] = dx[i + 1][j - 1];
            }
            dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + dx[i][j];
        }
    }
    while(q--){
        int l, r; cin >> l >> r;
        cout << dp[l][r] << el;
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 3003

string a, b;
int n, m, mod = 1e9 + 7;
long long dp[mxn][mxn];
 
void solve(){
    cin >> a >> b;
    n = a.size(); m = b.size();
    a = " " + a; b = " " + b;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i] == b[j]){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1;
            }else dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            dp[i][j] = (dp[i][j] + mod) % mod;
        }
    }
    cout << dp[n][m];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, s, a[105], dp[mxn];

void solve(){
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    dp[0] = 1;
    for(int i=1; i<=s; i++){
        for(int j=1; j<=n; j++){
            if(i >= a[j]){
                dp[i] += dp[i - a[j]];
                dp[i] %= mod;
            }
        }
    }
    cout << dp[s];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, s, a[105], dp[mxn];

void solve(){
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    dp[0] = 1;
    for(int i=1; i<=n; i++){
        for(int j=a[i]; j<=s; j++){
            dp[j] += dp[j - a[i]];
            dp[j] %= mod;
        }
    }
    cout << dp[s];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, a[105], dp[100005];

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    dp[0] = 1;
    set<int> s;
    for(int i=1; i<=n; i++){
        for(int j=1e5; j>=a[i]; j--){
            if(dp[j - a[i]] > 0){
                dp[j] = 1;
                s.insert(j);
            }
        }
    }
    cout << len(s) << el;
    for(int i : s) cout << i << ' ';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 1000006

int n, a[mxn], dp[mxn];

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    int res = 1;
    for(int i=n; i>=1; i--){
        dp[a[i]] = 1;
        for(int j=a[i]*2; j<=n; j+=a[i]){
            dp[a[i]] = max(dp[a[i]], dp[j] + 1);
        }
        res = max(res, dp[a[i]]);
    }
    cout << res << el;
    for(int i=1; i<=n; i++) dp[i] = -n;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 1000006

int n, k, dp[mxn], mod = 20051608;
 
void solve(){
    cin >> n >> k;
    for(int i=0; i<=k+1; i++) dp[i] = i + 1;
    for(int i=k+2; i<=n; i++){
        dp[i] = dp[i - 1] + dp[i - k - 1];
        dp[i] %= mod;
    }
    cout << dp[n];
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

int n, m, a[1005][1005], dp[1005][1005];
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
        }
    }
    int mx = 0, res = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j]){
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                if(dp[i][j] > mx){
                    mx = dp[i][j];
                    res = 1;
                }else if(dp[i][j] == mx) ++res;
            }
        }
    }
    cout << mx << ' ' << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 300005

int n, k, a[mxn], d[1005];

void solve(){
    cin >> n >> k;
    string s;
    for(int i=1; i<=n; i++){
        cin >> s;
        a[i] = s.size();
    }
    long long res = 0;
    for(int i=1; i<=n; i++){
        if(i > k + 1) --d[a[i - k - 1]];
        res += d[a[i]];
        ++d[a[i]];
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int f[1001];
void pre(){
    int n = 1e3;
    fo(i, 2, n) f[i] = oo;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int x = q.front(); q.pop();
        if(x == n) continue;
        fo(i, 1, x) if(x + x / i <= n){
            int y = x + x / i;
            if(f[x] + 1 < f[y]){
                f[y] = f[x] + 1;
                q.push(y);
            }
        }
    }
    // fo(i, 1, n) cout << f[i], el;
}

void LonggVuz(){
    int n, k; cin >> n >> k;
    int b[n+5], c[n+5];
    fo(i, 1, n) cin >> b[i];
    fo(i, 1, n) cin >> c[i];
    int sum = 0;
    fo(i, 1, n){
        sum += f[b[i]];
    }
    if(sum <= k){
        int res = 0;
        fo(i, 1, n) res += c[i];
        out(res);
    }
    vec<int> dp(k + 5);
    int cur = 0;
    fo(i, 1, n){
        int x = f[b[i]];
        fd(j, k, x) if(dp[j - x] + c[i] > dp[j]){
            dp[j] = dp[j - x] + c[i];
        }
    }
    int res = 0;
    fo(i, 0, k) res = max(res, dp[i]);
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    pre();
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}