[HG]AK 题解

前言

什么鬼畜玩意，扶我起来，我要用__int128，这辈子都不珂能用龟速乘的...

真香。

题解

我们知道这个模数是个神奇的东西

\(2305843008676823040 = 2^{29} \times 3 \times 5 \times 17 \times 65537\)

所以\(\varphi(2305843008676823040) = 2^{28} \times 2 \times 2^2 \times 2^4 \times 2^{16} = 2^{51}\)

\(a^{\varphi(n)}=1\ (mod\ n)\)，所以在\(60\)次以内，该数\(mod 2305843008676823040\)一定会变为\(1\)。

用线段树维护序列，再加一个龟速乘，解决问题

#include <cstdio>

#define ll long long

const ll MOD = 2305843008676823040ll;

ll s[1000001];

bool flg[1000001];

long long read(){

    long long x = 0; int zf = 1; char ch = ' ';

    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

    if (ch == '-') zf = -1, ch = getchar();

    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;

}

inline ll mul(ll x, ll y){

    ll res = 0;

    for ( ; y; y >>= 1ll, (x <<= 1ll) %= MOD)

        if(y & 1)

            (res += x) %= MOD;

    return res;

}

void build(int pos, int l, int r){

    if (l == r){

        s[pos] = read();

        flg[pos] = ((s[pos] == 1 || !s[pos]) ? 1 : 0);

        return ;

    }

    int mid = (l + r) >> 1;

    build(pos << 1, l, mid);

    build(pos << 1 | 1, mid + 1, r);

    flg[pos] = flg[pos << 1] & flg[pos << 1 | 1];

    s[pos] = (s[pos << 1] + s[pos << 1 | 1]) % MOD;

}

ll query(int pos, int l, int r, int x, int y){

    if (x <= l && r <= y && flg[pos])

        return s[pos];

    if (l == r){

        ll res = s[pos];

        ll tmp = mul(s[pos], s[pos]);

        if (tmp == s[pos])

            flg[pos] = 1;

        s[pos] = tmp;

        return res;

    }

    int mid = (l + r) >> 1;

    ll res;

    if (y <= mid)

        res = query(pos << 1, l, mid, x, y);

    else if (x > mid)

        res = query(pos << 1 | 1, mid + 1, r, x, y);

    else{

        res = query(pos << 1, l, mid, x, y);

        (res += query(pos << 1 | 1, mid + 1, r, x, y)) %= MOD;

    }

    s[pos] = (s[pos << 1] + s[pos << 1 | 1]) % MOD;

    flg[pos] = flg[pos << 1] & flg[pos << 1 | 1];

    return res

}

int main(){

    int n = read(), m = read();

    for (register int i = 1; i <= 1000000; ++i) flg[i] = 1;

    build(1, 1, n);

    while (m--){

        int l = read(), r = read();

        ll res = query(1, 1, n, l, r) % MOD;

        printf("%lld\n", res);

    }

    return 0;

}

巴特西

[HG]AK 题解

前言

题解

最新文章

热门文章