AtCoder Grand Contest 038 – 解题报告

A – 01 Matrix

这个题还是很思博的,直接挂题解的图:

https://img.atcoder.jp/agc038/editorial.pdf
// A.cpp
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n, m, A, B;
	scanf("%d%d%d%d", &n, &m, &B, &A);
	for (int i = 1; i <= n; i++, puts(""))
		for (int j = 1; j <= m; j++)
			if ((i <= A) ^ (j <= B))
				printf("1");
			else
				printf("0");
	return 0;
}
继续阅读AtCoder Grand Contest 038 – 解题报告

「QuestOJ」Product – 题解

主要思路

硬推就完事了:

\[ \begin{aligned} g(n) &= \sum_{i = 1}^n \frac{n}{\gcd(i, n)} = n \sum_{d|n} \frac{1}{d} \sum_{i = 1}^n [\gcd(n, i) = d] \\ &= n \sum_{d|n} \frac{1}{d} \sum_{i = 1}^{\frac{n}{d}} [\gcd(\frac{n}{d}, i) = 1] = \sum_{d|n} \frac{n}{d} \varphi(\frac{n}{d}) = \sum_{d|n} d \varphi(d) \\ &= \sum_{d|n} d^2 \prod_{p_i} (1 – \frac{1}{p_i}) = \prod_{p_i} (1 + \sum_{g = 1}^{e_i} p_i^{2g} (1 – \frac{1}{p_i}) ) \\ &= \prod_{p_i} (1 + \sum_{g = 1}^{e_i} p_i^{2g} – \sum_{g = 1}^{e_i} p_i^{2g – 1}) = \prod_{p_i} (1 + \sum_{g = 1}^{e_i} p_i^{2g} – \frac{ \sum_{g = 1}^{e_i} p_i^{2g} }{p_i} ) \\ &= \prod_{p_i} (1 + (1 – \frac{1}{p_i}) (\sum_{g = 1}^{e_i} p_i^{2g}) ) = \prod_{p_i} (1 + (1 – \frac{1}{p_i}) \frac{p_i^2 (1 – p_i^{2e_i})}{1 – p_i^2}) \\ &= \prod_{p_i} (1 + \frac{(p_i – 1)}{p_i} \frac{p_i^2 (1 – p_i^{2e_i})}{(1 – p_i)(1 + p_i)} ) \\ &= \prod_{p_i} (1 – \frac{p_i (1 – p_i^{2e_i})}{1 + p_i} ) = \prod_{p_i} \frac{1 + p_i – p_i + p_i^{2e_i + 1}}{1 + p_i} \\ &= \prod_{p_i} \frac{p_i^{2e_i + 1} + 1}{1 + p_i} \end{aligned} \]

最后上下除一下,得到:

\[ \frac{f(n)}{g(n)} = \prod_{p_i} (1 + p_i) \]

继续阅读「QuestOJ」Product – 题解

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:某个套路求和题 – 题解

「Codeforces」900D:Unusual Sequences – 题解

主要思路

首先先把 \(y\) 除掉一个 \(x\),并且我们发现可以用 \(2^{t – 1}\) 来算这个和为 \(y\) 的数列的个数。

知道这个之后,我们发现可以枚举 \(\frac{y}{x}\) 的质因子情况进行容斥。

继续阅读「Codeforces」900D:Unusual Sequences – 题解

「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]大数 – 题解