QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1177#744969#9738. Make It DivisiblekuguadawangkuguadawangFailed.2024-11-14 09:06:352024-11-14 09:06:35

Details

Extra Test:

Invalid Input

input:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
void solve()
{
    cout << 1 << '\n';
    cout << 50000 << ' ' << 1000000000 << '\n';
    for (int i = 1; i <= 50000; i += 2) {
        cout << 1 + i << ' ' << 735134401 + i << '\n';
    }
}
int main()
{
    i...

output:


result:

FAIL Expected integer, but "#include<bits/stdc++.h>" found (stdin, line 1)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744969#9738. Make It DivisiblekuguadawangTL 539ms4820kbC++234.7kb2024-11-14 01:05:182024-11-14 09:12:00

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
ll a[N];
ll b[N];
unordered_map<int, int> q;
int mul(int a, int b, int m)
{
    int r = a * b - m * (int)(1.L / m * a * b);
    return r - m * (r >= m) + m * (r < 0);
}
int mypow(int a, int b, int m)
{
    int res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
    {
        if (b & 1)
        {
            res = mul(res, a, m);
        }
    }
    return res;
}
int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
bool MR(int n)
{
    if (n <= 1)
        return 0;
    for (int p : B)
    {
        if (n == p)
            return 1;
        if (n % p == 0)
            return 0;
    }
    int m = (n - 1) >> __builtin_ctz(n - 1);
    for (int p : B)
    {
        int t = m, a = mypow(p, m, n);
        while (t != n - 1 && a != 1 && a != n - 1)
        {
            a = mul(a, a, n);
            t *= 2;
        }
        if (a != n - 1 && t % 2 == 0)
            return 0;
    }
    return 1;
}
int PR(int n)
{
    for (int p : B)
    {
        if (n % p == 0)
            return p;
    }
    auto f = [&](int x) -> int
    {
        x = mul(x, x, n) + 1;
        return x >= n ? x - n : x;
    };
    int x = 0, y = 0, tot = 0, p = 1, q, g;
    for (int i = 0; (i & 255) || (g = __gcd(p, n)) == 1; i++, x = f(x), y = f(f(y)))
    {
        if (x == y)
        {
            x = tot++;
            y = f(x);
        }
        q = mul(p, abs(x - y), n);
        if (q)
            p = q;
    }
    return g;
}
vector<int> fac(int n)
{
#define pb emplace_back
    if (n == 1)
        return {};
    if (MR(n))
        return {n};
    int d = PR(n);
    auto v1 = fac(d), v2 = fac(n / d);
    auto i1 = v1.begin(), i2 = v2.begin();
    vector<int> ans;
    while (i1 != v1.end() || i2 != v2.end())
    {
        if (i1 == v1.end())
        {
            ans.pb(*i2++);
        }
        else if (i2 == v2.end())
        {
            ans.pb(*i1++);
        }
        else
        {
            if (*i1 < *i2)
            {
                ans.pb(*i1++);
            }
            else
            {
                ans.pb(*i2++);
            }
        }
    }
    return ans;
}
vector<int> s;
vector<int> p;
unordered_map<int, int> f;

void dfs(int now, int sum) {
    // 2e3 * 5e4
    // 1e8
    if (now == s.size()) {
        p.push_back(sum);
        return ;
    }
    for (int i = 0; i <= f[s[now]]; i++) {
        dfs(now + 1, sum);
        sum = sum * s[now];
    }
}
void solve()
{
    q.clear();
    ll n, k;
    cin >> n >> k;
    vector<pair<int,int>> t;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i > 1) {
            if (a[i] == a[i - 1]) continue ;
            t.push_back({min(a[i], a[i - 1]), max(a[i], a[i - 1])});
        } 
    }
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    ll ss = 0;
    ll need = t.size();
    for (auto [x, y]: t)
    {
        ll add = y - x;
        f.clear();
        p.clear();
        s = fac(add);
        for (auto x: s) {
            f[x]++;
        }
        s.erase(unique(s.begin(), s.end()), s.end());
        dfs(0, 1);
        for (auto j: p) {
            if (j > x && j + add == y + (j - x) && (j - x) <= k) {
                q[j - x]++;
            }
        }
    }
    if (!need)
    {
        cout << k << ' ' << 1ll * k * (k + 1) / 2 << '\n';
        return;
    }
    ll sum = 0, ans = 0;
    for (auto [x, y] : q)
    {
        if (y != need)
            continue;
        for (int i = 1; i <= n; i++)
        {
            b[i] = a[i] + x;
        }
        bool use = 1;
        deque<int> s;
        for (int i = 1; i <= n; i++)
        {
            while (s.size() && s.back() > b[i])
            {
                ll x = b[i], y = s.back();
                if ((x % y) && (y % x))
                {
                    use = 0;
                    break;
                }
                s.pop_back();
            }
            if (s.size())
            {
                ll x = b[i], y = s.back();
                if ((x % y) && (y % x))
                {
                    use = 0;
                    break;
                }
            }
            s.push_back(b[i]);
        }
        if (use)
        {
            sum = sum + x;
            ans++;
        }
    }
    cout << ans << ' ' << sum << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}
/*
1 2
2 3


从小到大
20 10 2 10 20
*/