QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744865 | #9738. Make It Divisible | kuguadawang | WA | 0ms | 3612kb | C++23 | 1.8kb | 2024-11-14 00:01:00 | 2024-11-14 00:01:01 |
Judging History
你现在查看的是最新测评结果
- [2024-11-27 18:44:44]
- hack成功,自动添加数据
- (/hack/1263)
- [2024-11-14 09:10:13]
- hack成功,自动添加数据
- (/hack/1178)
- [2024-11-14 00:01: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;
void solve()
{
q.clear();
ll n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ll need = n - 1;
for (int i = 1; i < n; i++) {
ll x = a[i], y = a[i + 1];
if (x > y) {
swap(x, y);
} else if (x == y) {
need--;
}
ll add = y - x;
for (int j = 1; j * j <= add; j++) {
if ((add % j)) continue ;
if (j > x && j + add == y + (j - x) && (j - x) <= k) {
q[j - x]++;
}
ll now = add / j;
if (now == j) continue ;
if (now > x && now + add == y + (now - x) && (now - x) <= k) {
q[now - 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;
}
ll gcd = __gcd(b[1], b[2]);
bool use = 1;
for (int i = 2; i < n; i++) {
ll now = __gcd(b[i], b[i + 1]);
if (now < gcd) {
swap(now, gcd);
}
if (now % gcd) {
use = 0;
break;
}
}
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;
}
/*
(y + k) = (x + k) + now
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: -100
Wrong Answer
time: 0ms
memory: 3560kb
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 1 1 0 0 0 0
result:
wrong answer 2nd lines differ - expected: '0 0', found: '1 1'