QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#752147 | #9738. Make It Divisible | Proaes# | WA | 1ms | 3860kb | C++20 | 2.4kb | 2024-11-15 22:15:02 | 2024-11-15 22:15:03 |
Judging History
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'