概要

比赛地址

2020 Multi-University Training Contest 9

题目

1002. Absolute Math

题目大意：

令 f(n)=\sum_{d\mid n}|\mu(d)|
求 \sum_{i=1}^{m}f(ni)

一共 T(1\le T\le 10^4) 组数据，1\le n,m\le 10^7.

解题思路：

由莫比乌斯函数的定义，当其 d 对答案有贡献时，当且仅当其不含有平方因子。设 n 有 w(n) 个不同的质因子。每个质因子的次数只有取 0 或 1 时才会有贡献。因此，

f(n)=\sum_{d\mid n}|\mu(d)|=2^{w(n)}

我们发现 f(n) 是一个积性函数：

f(nm)=\frac{f(n)\cdot f(m)}{f(gcd(n,m))}

开始推柿子：

\begin{aligned}
&\ \ \ \ \ \sum_{i=1}^{m}f(ni)\cr
&=\sum_{i=1}^{m}\frac{f(n)f(i)}{f(gcd(n,i))}\cr
&=f(n)\sum_{d\mid n}\sum_{i=1}^{m}\frac{f(i)}{f(d)}\cdot [gcd(n,i)=d]\cr
&=f(n)\sum_{d\mid n}\sum_{i=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\frac{f(id)}{f(d)}\cdot [gcd(\frac{n}{d},i)=1]\cr
&=f(n)\sum_{d\mid n}\frac{1}{f(d)}\sum_{i=1}^{\left\lfloor\frac{m}{d}\right\rfloor}f(id)\sum_{p\mid gcd(\frac{n}{d},i)}\mu(p)\cr
&=f(n)\sum_{d\mid n}\frac{1}{f(d)}\sum_{p\mid \frac{n}{d}}\mu(p)\sum_{i=1}^{\left\lfloor\frac{m}{pd}\right\rfloor}f(ipd)
\end{aligned}

枚举 T=pd：

\begin{aligned}
&=f(n)\sum_{T\mid n}\sum_{i=1}^{\left\lfloor\frac{m}{T}\right\rfloor}f(iT)\sum_{d\mid T}\frac{\mu\left(\frac{T}{d}\right)}{f(d)}\cr
&=f(n)\sum_{T\mid n}\left(\frac{1}{f(T)} * \mu(T)\right)\sum_{i=1}^{\left\lfloor\frac{m}{T}\right\rfloor}f(iT)\cr
&=f(n)\sum_{T\mid n}g(T)\sum_{i=1}^{\left\lfloor\frac{m}{T}\right\rfloor}f(iT)
\end{aligned}

令：

g(n)=\frac{1}{f(n)} * \mu(n)

我们发现 g(n) 也是一个积性函数。其中，g(1)=1，g(p)=-\frac{1}{2}，g(p^k)=0。因此我们可以线性筛出 g。又有 g(T) 对答案产生贡献，当且仅当 T 分解质因数后无平方因子。由于 w(n)\le 8，对于每个询问，我们可以枚举全部的 T。

对于后半部分式子的处理，我们可以考虑离线全部的询问，记录每个询问所对应的 T、n、\left\lfloor\frac{m}{T}\right\rfloor\cdot T。按照 T 为第一关键字、\left\lfloor\frac{m}{T}\right\rfloor 为第二关键字进行排序，对于相同的 T，我们无需重新累加，即每个 T 计算 \frac{\max (m)}{T} 次。假定所有 T\in [1,n] 都被计算一次，这部分复杂度为 O(nlog_n)

加上枚举每个 n 所对应 T 的复杂度，一共是 O(nlog_n+T\cdot 2^8)。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
const int N = 1e7 + 50;
const int rinv2 = P - (P + 1) / 2;
int n, m;

int prime[N], num[N], f[N], g[N], tot;
void init() {
    f[1] = g[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!num[i]) {
            prime[++tot] = i;
            f[i] = 2; g[i] = rinv2;
        }
        for (int j = 1; j <= tot && prime[j] * i < N; j++) {
            num[prime[j] * i] = 1;
            if (i % prime[j]) {
                f[i * prime[j]] = 2 * f[i] % P;
                g[i * prime[j]] = 1LL * g[i] * rinv2 % P;
            }
            else {
                f[i * prime[j]] = f[i];
                break;
            }
        }
    }
}

struct Data {
    int T, up, n, id;
};

vector<Data> data;
vector<int> fac;
int ans[N];

void getfac(int n) {
    for (int i = 1; prime[i] * prime[i] <= n; i++) {
        if (n % prime[i] == 0) {
            fac.push_back(prime[i]);
            while (n % prime[i] == 0) {
                n /= prime[i];
            }
        }
    }
    if (n != 1) {
        fac.push_back(n);
    }
}

void dfs(int now, int d, vector<int> &v, int id) {
    if (now == v.size()) {
        data.push_back((Data){d, (m / d) * d, n, id});
        return;
    }
    dfs(now + 1, d, v, id);
    int D = d * v[now];
    if (D <= m) {
        dfs(now + 1, D, v, id);
    }
}

int main() {
    init();
    int kase; scanf("%d", &kase);
    for (int = 1; <= kase; ++) {
        fac.resize(0);
        scanf("%d%d", &n, &m);
        getfac(n);
        dfs(0, 1, fac,);
    }
    sort(data.begin(), data.end(), [&](Data a, Data b) {
        return a.T == b.T ? a.up < b.up : a.T < b.T;
    });
    long long sum = 0; int i = 0, T = 0;
    for (auto dt : data) {
        int tmp = 1LL * f[dt.n] * g[dt.T] % P;
        if (T != dt.T) {
            sum = 0; i = T = dt.T;
        }
        for (; i <= dt.up; i += T) {
            sum += f[i];
        }
        (ans[dt.id] += sum % P * tmp % P) %= P;
    }
    for (int i = 1; i <= kase; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

1003. Slime and Stones

题目大意

有两堆石子，有两种拿取的方式：第一，在一堆中拿任意多个石子；第二，在两堆中拿相差不能超过 k 的石子个数。没有石子可拿的玩家判负。问最后谁赢。

解题思路

当 k=0 时，问题退化为威佐夫博弈，先手必败点为：

(1,2), (3,5), (4,7), (6,10)\cdots ,(a_n,b_n)

当 k=1 时，打表得先手必败点为：

(1,3), (2,6), (4,10), (5,13),\cdots ,(a_n,b_n)

设 a_n=\alpha \cdot n，b_n=\beta\cdot n。注意到，全部的 a_i、b_i 互不相同且其并集为自然数集，构成了 beatty 序列。又根据打表得出的结果，b_n=a_n+n\cdot (k+1)，因此 \beta=\alpha+k+1。

由 beatty 序列相关知识，有式子：

\frac{1}{\alpha}+\frac{1}{\beta}=1

因此：

\frac{1}{\alpha}+\frac{1}{\alpha+k+1}=1

解得：

\alpha=\frac{\sqrt{k^2+2k+5}+1-k}{2}

因此当且仅当：

\frac{b-a}{k+1}\cdot \alpha=a

时，为先手必败点。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T; scanf("%d", &T);
    while(T--){
        long long a, b, k;
        scanf("%lld%lld%lld", &a, &b, &k);
        if(a > b) swap(a, b);
        long long x = b - a;
        if(x % (k + 1) != 0) {
            puts("1");
            continue;
        }
        x /= (k + 1);
        double n = (double)(sqrt((k * k + 2 * k + 5)) + 1 - k) / 2.0;
        x = floor(n * x);
        puts(x == a ? "0" : "1");
    }
    return 0;
}