LibreOJ#6181:某个套路求和题 – 题解

主要思路

好题目啊。

发现 \(f(x)\) 对于有平方因子的数都没有效益,所以我们只考虑 \(f(x) = \prod_{i = 1}^m p_i\)。那么很容易发现 \(f(x) = \prod_{r = 0}^m (-1)^{2^{(r – 1)}}\),所以:

\[ f(x) = \begin{cases} -1, x \in primes or x = 1 \\ 1, otherwise \end{cases} \]

继续阅读LibreOJ#6181:某个套路求和题 – 题解

「LibreOJ」#6682. 梦中的数论 – 题解

主要思路

其实稍稍看一下,会发现 \([j|i][(j + k)|i]\) 满足的时候 \(k\) 并没有什么特别的限制,所以可以直接理解为选两个因数,然后就转化为了:

\[ \begin{aligned} & \sum_{i = 1}^n {\sigma_0(i) \choose 2} \\ =& \sum_{i = 1}^n \frac{\sigma_0^2(i) – \sigma_0(i)}{2}\end{aligned} \]

后面的那个 \(\sum \sigma_0(x)\) 可以直接数论分块,前面那个用 min_25 筛一下就好。有 \(f(p^k) = \prod (1 + c_i)^2\)。

继续阅读「LibreOJ」#6682. 梦中的数论 – 题解

P3245:[HNOI2016]大数 – 题解

主要思路

佛了。

让 \(p\) 跟 \(10\) 取个 \(\gcd\)。如果互质的话就是数数列 \(a_i = \text{从 i 到 n 表示的数字} \bmod p\) 区间里的同色对数,用莫队搞即可;如果是 \(2\) 那就把 \(0, 2, 4, 6, 8\) 这些尾数染颜色然后数同色对数,这个可以 \(\Theta(n)\),如果是 \(5\) 那就把 \(0, 5\) 染色即可。

继续阅读P3245:[HNOI2016]大数 – 题解

P3589:[POI2015]KUR – 题解

主要思路

乍一看很难直接做,我们考虑从那个长度为 \(m\) 的串开始搞,发现每个 \(01\) 都对应的是一个不等式条件:

\[ a(s + i) + b < p \]

其中在 \(m\) 串的位置中为 \(i\),在 \(S\) 中的位置为 \(s + i\)。列了这么多之后进行区间交,然后发现性质 \(\gcd(a, n) = 1\),代表 \(ai \bmod n\) 是一一对应的,所以我们求最后的值的个数只需要减去 \([n – m + 1, n – 1]\) 内符合条件的数即可。

代码

// P3589.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int n, a, b, p, m, ltot;
char str[MAX_N];
pair<int, int> limits[MAX_N << 2];

void create(int l, int r)
{
    if (l <= r)
        limits[++ltot] = make_pair(l, r);
    else
        limits[++ltot] = make_pair(l, n - 1), limits[++ltot] = make_pair(0, r);
}

int main()
{
    scanf("%d%d%d%d%d%s", &n, &a, &b, &p, &m, str);
    int ans = 0;
    for (int i = 0; i < m; i++)
        if (str[i] == '0')
            create((p + n - 1LL * i * a % n) % n, (0LL + n - 1 - 1LL * i * a % n) % n);
        else
            create((n - 1LL * i * a % n) % n, (p + n - 1LL * i * a % n - 1) % n);
    for (int i = 1; i < m; i++)
        create((0LL + b + n - 1LL * a * i % n) % n, (0LL + b + n - 1LL * a * i % n) % n);
    sort(limits + 1, limits + 1 + ltot);
    int tmp = -1;
    for (int i = 1; i <= ltot; i++)
    {
        if (limits[i].first > tmp)
            ans += limits[i].first - tmp - 1, tmp = limits[i].second;
        else
            tmp = max(tmp, limits[i].second);
    }
    printf("%d\n", ans + n - 1 - tmp);
    return 0;
}