这个题还是很思博的，直接挂题解的图：
// 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;
}
Continue reading → 硬推就完事了：
\[ \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) \]
Continue reading →好题目啊。
发现 \(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} \]
Continue reading →首先先把 \(y\) 除掉一个 \(x\)，并且我们发现可以用 \(2^{t – 1}\) 来算这个和为 \(y\) 的数列的个数。
知道这个之后，我们发现可以枚举 \(\frac{y}{x}\) 的质因子情况进行容斥。
Continue reading →其实稍稍看一下，会发现 \([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\)。
Continue reading →佛了。
让 \(p\) 跟 \(10\) 取个 \(\gcd\)。如果互质的话就是数数列 \(a_i = \text{从 i 到 n 表示的数字} \bmod p\) 区间里的同色对数，用莫队搞即可；如果是 \(2\) 那就把 \(0, 2, 4, 6, 8\) 这些尾数染颜色然后数同色对数，这个可以 \(\Theta(n)\)，如果是 \(5\) 那就把 \(0, 5\) 染色即可。
Continue reading →