QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#752147#9738. Make It DivisibleProaes#WA 1ms3860kbC++202.4kb2024-11-15 22:15:022024-11-15 22:15:03

Judging History

你现在查看的是最新测评结果

  • [2024-11-27 18:44:44]
  • hack成功,自动添加数据
  • (/hack/1263)
  • [2024-11-15 22:15:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3860kb
  • [2024-11-15 22:15:02]
  • 提交

answer

/**
 *    title:  m.cpp
 *    author:  Proaes Meluam
 *    created:  2024-11-15 21:39:02
**/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h" 
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double pi = acos(-1);
const double E = exp(1);
constexpr ll mod = 1e9 + 7;
// constexpr int inf = 0x3f3f3f3f;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    auto frac = [&](ll x) {
        vector<ll> f;
        // f.emplace_back(1);
        for (ll i = 1; i * i <= x; ++ i) {
            if (x % i == 0) {
                if (i != x / i) {
                    f.emplace_back(i);
                    f.emplace_back(x / i);
                } else {
                    f.emplace_back(i);
                }
            }
        }
        sort(f.begin(), f.end());
        return f;
    };

    int tt = 1;
    cin >> tt;
    while (tt--) {
        ll ans1 = 0, ans2 = 0;
        ll n, k, minb = inf;
        cin >> n >> k;
        vector<ll> b(n + 1);
        for (int i = 1; i <= n; ++ i) {
            cin >> b[i];
            minb = b[i];
        }
        auto check = [&](ll x) -> bool {
            if (x > 0) {
                bool res = 1;
                vector<ll> a(n + 1);
                for (int i = 1; i <= n; ++ i) {
                    a[i] = b[i] + x;
                    if (i > 1) {
                        if (a[i] % a[i - 1] == 0 || a[i - 1] % a[i] == 0) {

                        } else {
                            res = 0;
                            break;
                        }
                    }
                    
                }
                return res;
            } else {
                return 0;
            }
        };
        if (n == 1) {
            ans1 = k;
            ans2 = k * (k + 1ll) / 2ll;
        } else {
            ll g = b[2] - b[1];
            for (int i = 3; i <= n; ++ i) {
                g = gcd(g, b[i] - b[i - 1]);
            }
            vector<ll> fg = frac(g);
            // debug(g);
            // debug(fg);
            for (auto y : fg) {
                ll x = y - minb;
                // debug(x);
                if (check(x)) {
                    ans1 += 1;
                    ans2 += x;
                }
            }
        }
        cout << ans1 << " " << ans2 << "\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

input:

3
5 10
7 79 1 7 1
2 1000000000
1 2
1 100
1000000000

output:

3 8
0 0
100 5050

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

4
201 1000000000
1 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5...

output:

0 0
0 0
0 0
0 0

result:

ok 4 lines

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3616kb

input:

500
4 1000000000
8 14 24 18
4 1000000000
17 10 18 14
4 1000000000
6 17 19 19
4 1000000000
15 14 15 25
4 1000000000
16 16 5 25
4 1000000000
4 30 20 5
4 1000000000
11 4 23 9
4 1000000000
14 25 13 2
4 1000000000
18 18 1 15
4 1000000000
22 22 22 28
4 1000000000
15 17 17 10
4 1000000000
22 14 13 25
4 100...

output:

0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
...

result:

wrong answer 178th lines differ - expected: '1 2', found: '0 0'