QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#769782 | #9738. Make It Divisible | wht11 | RE | 92ms | 19984kb | C++20 | 2.8kb | 2024-11-21 19:23:00 | 2024-11-21 19:23:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int t = 1, n, k;
int l[N], r[N];
int st[N][20], a[N]; // 区间长度最大不超过2^20
int Log[N];
int gcd(int a, int b)
{
if (!b)
return a;
else
return gcd(b, a % b);
}
int query(int l, int r)
{
int k = Log[r - l + 1];
return gcd(st[l][k], st[r - (1 << k) + 1][k]);
}
int check(int x)
{
vector<int> b(n + 3);
for (int i = 1; i <= n; i++)
b[i] = a[i] + x;
/* for (int i = 1; i <= n; i++)
cerr << b[i] << " ";
cerr << endl; */
for (int i = 1; i <= n; i++)
st[i][0] = b[i];
for (int j = 1; j <= Log[n]; j++)
{
for (int i = 1; i <= n; i++)
{
st[i][j] = gcd(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
}
for (int i = 1; i <= n; i++)
{
int d = query(l[i], r[i]);
if (d != b[i])
return 0;
}
return 1;
}
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
l[0] = 0;
r[n + 1] = n + 1;
deque<int> q;
q.push_back(0);
for (int i = 1; i <= n; i++)
{
while (!q.empty() && a[q.back()] >= a[i])
q.pop_back();
if (!q.empty())
l[i] = q.back();
q.push_back(i);
}
q.clear();
q.push_back(n + 1);
for (int i = n; i >= 1; i--)
{
while (!q.empty() && a[q.back()] >= a[i])
q.pop_back();
if (!q.empty())
r[i] = q.back();
q.push_back(i);
}
for (int i = 1; i <= n; i++)
{
l[i]++;
r[i]--;
// cerr << l[i] << " " << r[i] << endl;
}
int w = 0;
int lst = 0;
for (int i = 2; i <= n; i++)
{
if (a[i] != a[i - 1])
{
w = abs(a[i] - a[i - 1]);
lst = min(a[i], a[i - 1]);
}
}
if (w == 0)
{
cout << k << " " << k * (k + 1ll) / 2ll << "\n";
return;
}
vector<int> ve;
// cerr << w << endl;
for (int i = 1; i * i <= w; i++)
{
if (w % i == 0)
{
ve.push_back(i);
if (i * i != w)
ve.push_back(w / i);
}
}
int cnt = 0, sum = 0;
for (auto x : ve)
{
// cerr << x << " ";
int c = x - lst;
if (c >= 1 && c <= k)
{
if (check(c))
{
cnt++;
sum += c;
}
}
}
cout << cnt << " " << sum << "\n";
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Log[1] = 0;
for (int i = 2; i < N; i++)
Log[i] = Log[i / 2] + 1;
cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11516kb
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: 11272kb
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: 0
Accepted
time: 2ms
memory: 11928kb
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:
ok 500 lines
Test #4:
score: 0
Accepted
time: 92ms
memory: 19984kb
input:
1 50000 1000000000 230 286458 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 ...
output:
0 0
result:
ok single line: '0 0'
Test #5:
score: 0
Accepted
time: 50ms
memory: 17728kb
input:
1 50000 1000000000 12087 1196491 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 553146...
output:
0 0
result:
ok single line: '0 0'
Test #6:
score: 0
Accepted
time: 22ms
memory: 17992kb
input:
1 50000 1000000000 2138984 42249920 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 3581...
output:
0 0
result:
ok single line: '0 0'
Test #7:
score: -100
Runtime Error
input:
500 39 1000000000 75 7 7 381 41 1197 177 177 41 109 109 16 1197 177 41 381 1605 381 381 7 177 177 177 177 177 177 177 177 7 7 143 143 143 143 143 653 143 823 7 61 1000000000 327 327 327 327 405153474 327 405153474 327 810306621 810306621 810306621 810306621 810306621 810306621 810306621 810306621 81...