QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786012 | #9738. Make It Divisible | xyggzsf# | WA | 0ms | 3548kb | C++14 | 1.4kb | 2024-11-26 19:55:24 | 2024-11-26 19:55:36 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
#define int long long
typedef pair<int, int>pii;
typedef pair<char, int>pci;
typedef pair<int, pii>piii;
const int mod = 998244353;
const int N = 5e5 + 100;
int n, k;
int a[N];
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
if (n == 1) {
cout << k << ' ' << ((k + 1) * k / 2)<<endl;
return;
}
int temp = a[2] - a[1];
for (int i = 3; i <= n; i++) temp = gcd(temp, a[i] - a[i - 1]);
vector<int> v;
for (int i = 1; i*i <= temp; i++) {
if (temp % i == 0) {
v.push_back(i);
v.push_back(temp / i);
}
}
int ans=0, ans_sum = 0;
for (auto t : v) {
if (t-a[1] > k) continue;
if (t <= a[1]) continue;
int yu = a[1] % t;
bool flag = false;
for (int i = 1; i <= n; i++) {
if (a[i] % t != yu) flag=true;
}
if (flag) continue;
ans++;
ans_sum += t-a[1];
//cout << t << endl;
}
cout << ans << ' ' << ans_sum << endl;
}
signed main()
{
ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
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: 3544kb
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'