Subtask ~1~

Với mỗi testcase, ta duyệt từ ~1~ đến ~n-1~ và vừa tính giai thừa vừa ~\bmod~ để tránh tràn số, gặp số thỏa mãn ~\bmod x = 0~ thì cập nhật đáp án.

Code tham khảo

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

int x;

long long giai_thua(int n)
{
    long long ans = 1;
    for(int i = 1; i <= n; i ++)
    {
        ans = ans*i;
        ans = ans % x;
    }
    return ans;
}

int main()
{
    int t; cin >> t;
    while(t--)
    {
        cin >> x;
        int result = 0;
        for(int i = 1; i < x; i++)
            if ((giai_thua(i) + giai_thua(i-1)) % x == 0)
                result = max(i, result);
        cout << result << '\n';
    }
    return 0;
}

Subtask ~2~

Thay vì duyệt xuôi, ta duyệt lùi từ ~n-1~ đến ~1~ và dừng ngay khi gặp số thỏa mãn sẽ cải thiện thời gian chạy đáng kể.

Code tham khảo

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

int x;

long long giai_thua(int n)
{
    long long ans = 1;
    for(int i = 1; i <= n; i ++)
    {
        ans = ans*i;
        ans = ans % x;
    }
    return ans;
}

int main()
{
    int t; cin >> t;
    while(t--)
    {
        cin >> x;
        for(int i = x-1; i > 0; i++)
            if ((giai_thua(i) + giai_thua(i-1)) % x == 0){
                cout << i << '\n';
                break;
            }
    }
    return 0;
}

Subtask ~3~

Nhận thấy ~n~ có thể lên đến ~10^{12}~ là quá lớn để duyệt, ta cần phải biến đổi để tối ưu thuật toán. Dựa vào công thức đệ quy trên ta có:

~S = n! + (n-1)! ~

~\Leftrightarrow S = n \times (n-1)! + (n-1)!~

~\Leftrightarrow S = (n + 1) \times (n-1)!~

Đến đây có thể dàng nhận thấy, ~n+1 = x~ đồng thời chia hết cho ~x~ và thỏa mãn ~n~ lớn nhất nhỏ hơn ~x~. Vậy đáp án của bài toán là ~x-1~.

Code tham khảo

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

long long x;

int main()
{
    int t; cin >> t;
    while(t--)
    {
        cin >> x;
        cout << x-1 << '\n';
    }
    return 0;
}