Loading [MathJax]/extensions/tex2jax.js

LibreOJ 3096:「SNOI2019」数论题解

解法

首先我们在\(Q\)的剩余系内枚举数\(x_0\),对于此每个数表示成\(x = (x_0 + k * P) \mod Q\),思考一下发现这些数会随着\(k\)变化,且这些数会呈现周期性规律:也就是这些数在一个环上,我们可以考虑记录\(Q\)剩余系中每一个数在\(P\)中的贡献,记录成前缀和,计算答案时比较排名来判断环的方向(长弧或是短弧)。

具体看代码吧,细细品味一下应该就能理解了。

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// LOJ3096.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 2000;
ll p, q, n, m, t, ai[MAX_N], bi[MAX_N], sum[MAX_N], tot[MAX_N], len, ans;
int key[MAX_N], rk[MAX_N];
bool vis[MAX_N];
ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y); }
int main()
{
scanf("%lld%lld%lld%lld%lld", &p, &q, &n, &m, &t);
len = q / gcd(p, q);
for (int i = 1; i <= n; i++)
scanf("%lld", &ai[i]);
for (int i = 1; i <= m; i++)
{
scanf("%lld", &bi[i]), sum[bi[i]]++;
key[bi[i]] = 1;
}
for (int i = 0; i < q; i++)
{
if (vis[i])
continue;
vis[i] = true;
int now, last = i;
rk[i] = 1;
for (now = (last + p) % q; now != i; last = now, now = (now + p) % q)
rk[now] = rk[last] + 1, sum[now] += sum[last], vis[now] = true;
tot[i] = sum[last];
for (int j = (i + p) % q; j != i; j = (j + p) % q)
tot[j] = sum[last];
}
for (int i = 1; i <= n; i++)
{
if (ai[i] >= t)
continue;
ll cnt = (t - 1 - ai[i]) / p;
ll A = ai[i] % q, B = (A + cnt % len * p) % q;
ans += cnt / len * tot[A];
if (rk[A] <= rk[B])
ans += sum[B] - sum[A] + key[A];
else
ans += tot[A] - (sum[A] - sum[B] - key[A]);
}
printf("%lld", ans);
return 0;
}
// LOJ3096.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 1e6 + 2000; ll p, q, n, m, t, ai[MAX_N], bi[MAX_N], sum[MAX_N], tot[MAX_N], len, ans; int key[MAX_N], rk[MAX_N]; bool vis[MAX_N]; ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y); } int main() { scanf("%lld%lld%lld%lld%lld", &p, &q, &n, &m, &t); len = q / gcd(p, q); for (int i = 1; i <= n; i++) scanf("%lld", &ai[i]); for (int i = 1; i <= m; i++) { scanf("%lld", &bi[i]), sum[bi[i]]++; key[bi[i]] = 1; } for (int i = 0; i < q; i++) { if (vis[i]) continue; vis[i] = true; int now, last = i; rk[i] = 1; for (now = (last + p) % q; now != i; last = now, now = (now + p) % q) rk[now] = rk[last] + 1, sum[now] += sum[last], vis[now] = true; tot[i] = sum[last]; for (int j = (i + p) % q; j != i; j = (j + p) % q) tot[j] = sum[last]; } for (int i = 1; i <= n; i++) { if (ai[i] >= t) continue; ll cnt = (t - 1 - ai[i]) / p; ll A = ai[i] % q, B = (A + cnt % len * p) % q; ans += cnt / len * tot[A]; if (rk[A] <= rk[B]) ans += sum[B] - sum[A] + key[A]; else ans += tot[A] - (sum[A] - sum[B] - key[A]); } printf("%lld", ans); return 0; }
// LOJ3096.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX_N = 1e6 + 2000;
ll p, q, n, m, t, ai[MAX_N], bi[MAX_N], sum[MAX_N], tot[MAX_N], len, ans;
int key[MAX_N], rk[MAX_N];
bool vis[MAX_N];

ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y); }

int main()
{
    scanf("%lld%lld%lld%lld%lld", &p, &q, &n, &m, &t);
    len = q / gcd(p, q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]);
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld", &bi[i]), sum[bi[i]]++;
        key[bi[i]] = 1;
    }
    for (int i = 0; i < q; i++)
    {
        if (vis[i])
            continue;
        vis[i] = true;
        int now, last = i;
        rk[i] = 1;
        for (now = (last + p) % q; now != i; last = now, now = (now + p) % q)
            rk[now] = rk[last] + 1, sum[now] += sum[last], vis[now] = true;
        tot[i] = sum[last];
        for (int j = (i + p) % q; j != i; j = (j + p) % q)
            tot[j] = sum[last];
    }
    for (int i = 1; i <= n; i++)
    {
        if (ai[i] >= t)
            continue;
        ll cnt = (t - 1 - ai[i]) / p;
        ll A = ai[i] % q, B = (A + cnt % len * p) % q;
        ans += cnt / len * tot[A];
        if (rk[A] <= rk[B])
            ans += sum[B] - sum[A] + key[A];
        else
            ans += tot[A] - (sum[A] - sum[B] - key[A]);
    }
    printf("%lld", ans);
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *