NOI模拟题5 Problem A: 开场题

Solution

注意到$\gcd$具有结合律:

\[
\gcd(a, b, c) = \gcd(a, \gcd(b, c))
\]

因此我们从后往前, 对于每个位置$L$, 找到每一段不同的$\gcd(a_x, a_{x + 1}, \cdots, a_R)$. 我们注意到这样的$R$最多只有$\log$段.

每个位置合并其后面一个位置的信息.

同时我们还维护序列的前缀异或和, 对于每个异或值, 都开一颗线段树来存储其出现的位置. 随便乱搞即可.

#include <cstdio>

#include <cctype>

#include <vector>

#include <algorithm>

#include <map>

typedef long long LL;

using namespace std;

namespace Zeonfai

{

    inline LL getLL()

    {

        LL a = 0, sgn = 1; char c;

        while (! isdigit(c = getchar())) if (c == '-') sgn *= -1;

        while (isdigit(c)) a = a * 10 + c - '0', c = getchar();

        return a * sgn;

    }

}

const int N = (int)1e5, INF = (int)2e9;

int n;

LL a[N + 1], sum[N + 1];

struct record

{

    int ed; LL val;

    inline record(int _ed, LL _val) { ed = _ed; val = _val; }

};

vector<record> bck[N + 1];

map<LL, int> mp;

struct segmentTree

{

    struct node

    {

        node *suc[2];

        inline node() { for (int i = 0; i < 2; ++ i) suc[i] = NULL; }

    }*rt;

    inline segmentTree() { rt = NULL; }

    node *insert(node *u, int L, int R, int pos)

    {

        if (u == NULL) u = new node;

        if (L == R) return u;

        if (pos <= L + R >> 1) u->suc[0] = insert(u->suc[0], L, L + R >> 1, pos);

        else u->suc[1] = insert(u->suc[1], (L + R >> 1) + 1, R, pos);

        return u;

    }

    inline void insert(int pos) { rt = insert(rt, 1, n, pos); }

    int find(node *u, int curL, int curR, int L, int R)

    {

        if (u == NULL) return INF;

        if (curL == curR) return curL;

        int res = INF, mid = curL + curR >> 1;

        if (L <= mid) res = min(res, find(u->suc[0], curL, mid, L, R));

        if (res == INF && R > mid) res = min(res, find(u->suc[1], mid + 1, curR, L, R));

        return res;

    }

    inline int find(int L, int R) { return find(rt, 1, n, L, R); }

}seg[N];

/* inline LL __gcd(LL a, LL b)

{

    if (a < b) swap(a, b);

    while (b)

    {

        LL tmp = b;

        b = a % b;

        a = tmp;

    }

    return a;

} */

inline vector<record>::iterator getPrevious(vector<record>::iterator p) { return -- p; }

int main()

{

#ifndef ONLINE_JUDGE

    freopen("start.in", "r", stdin);

    freopen("start.out", "w", stdout);

#endif

    using namespace Zeonfai;

    n = getLL();

    for (int i = 1; i <= n; ++ i) a[i] = getLL();

    for (int i = n; i; -- i)

    {

        bck[i].push_back(record(i, a[i])); int tot = 1;

        if (i != n)

        {

            for (vector<record>::iterator p = bck[i + 1].begin(); p != bck[i + 1].end(); ++ p)

                if (__gcd(p->val, a[i]) != bck[i][tot - 1].val)

                    bck[i].push_back(record(p->ed, __gcd(a[i], p->val))), ++ tot;

                else bck[i][tot - 1].ed = p->ed;

        }

    }

    sum[0] = 0; mp.clear(); int tot = 0;

    for (int i = 1; i <= n; ++ i)

    {

        sum[i] = sum[i - 1] ^ a[i];

        if (mp.find(sum[i]) == mp.end()) mp[sum[i]] = tot ++;

        seg[mp[sum[i]]].insert(i);

    }

    LL K = getLL();

    for (int i = 1; i <= n; ++ i)

    {

        for (vector<record>::iterator p = bck[i].begin(); p != bck[i].end(); ++ p)

        {

            if (K % p->val) continue;

            int res = INF;

            if (mp.find(K / p->val ^ sum[i - 1]) != mp.end())

                res = seg[mp[K / p->val ^ sum[i - 1]]].find(p == bck[i].begin() ? i : getPrevious(p)->ed + 1, p->ed);

            if (res != INF)

            {

                printf("%d %d\n", i, res);

                return 0;

            }

        }

    }

    puts("no solution");

}

巴特西

NOI模拟题5 Problem A: 开场题

Solution

最新文章

热门文章