Kalorona

「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) \]

Continue reading →

AtCoder Grand Contest 045 – 解题报告

A – Xor Battle

感觉有点傻逼啊。

对于 0 而言，我们只需要最后的答案为 0 即可。那么，我们从后往前进行维护，维护 \(0\) 位置上权值组合而成的线性基，然后每次到 \(1\) 位置的时候就在里面查即可，如果没查到，那么对于 \(1\) 而言，后面的 \(0\) 并不足以抵消该操作，所以可以判 \(1\) 获胜，亦而反之。

Continue reading →

AtCoder Grand Contest 046 – 解题报告

A – Takahashikun, The Strider

SB 题，不解释。

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

using namespace std;

int x;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    scanf("%d", &x), printf("%d\n", 360 / gcd(x, 360));
    return 0;
}
Continue reading →