QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#757974#9738. Make It DivisibleFalse0099WA 0ms3860kbC++201.8kb2024-11-17 14:56:252024-11-17 14:56:35

Judging History

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

  • [2024-11-27 18:44:44]
  • hack成功,自动添加数据
  • (/hack/1263)
  • [2024-11-17 14:56:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3860kb
  • [2024-11-17 14:56:25]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
int INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
typedef pair<int, int> PII;
void init()
{
}
void solve()
{
    int n, l;
    cin >> n >> l;
    vector<int> d(n + 1);
    vector<int> a(n + 1);
    int ggcd = 0;
    int minn = INF;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        minn = min(minn, a[i]);
        d[i] = abs(a[i] - a[i - 1]);
        if (i != 1)
        {
            ggcd = __gcd(ggcd, d[i]);
        }
    }
    set<int> st;
    if (ggcd == 0)
    {
        cout << l << " ";
        cout << (1 + l) * l / 2 << endl;
        return;
    }
    int sum = 0;
    for (int i = 1; i * i <= ggcd; i++)
    {
        if (ggcd % i == 0)
        {
            int u = i;
            int k = u - minn;
            if (k > 0 && k <= l)
            {
                if (__gcd(a[1] + k, ggcd) == u)
                {
                    st.insert(k);
                    sum += k;
                }
            }
            int v = ggcd / i;
            k = v - minn;
            if (k > 0 && k <= l)
            {
                if (__gcd(a[1] + k, ggcd) == v)
                {
                    st.insert(k);
                    sum += k;
                }
            }
        }
    }
    for (int i = 1; i <= n - 1; i++)
    {
        set<int> st1 = st;
        for (auto u : st)
        {
            if (__gcd(a[i] + u, a[i + 1] + u) != min(a[i], a[i + 1]) + u)
            {
                st1.erase(u);
                sum -= u;
            }
        }
        st = st1;
    }
    cout << st.size() << " " << sum << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    t = 1;
    cin >> t;
    init();
    while (t--)
    {
        solve();
    }
}

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: -100
Wrong Answer
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
1 1
0 0
0 0

result:

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