Oql's Blog

发表于 分类于

题意

定义一函数 $f$：

$$f(n)=\begin{cases}
1 & \text{ if } n=1 \
p \bigoplus c & \text{ if } n=p^c,p\in \mathbb{P} \
f(a)f(b) & \text{ if } n=ab,\gcd(a,b)=1
\end{cases}$$

求 $\sum_{i=1}^{n}f(i)$ 的值。

$n\leq 10^{10}$

阅读全文 »

发表于 分类于

题意

一个 $n$ 个点的树，点有点权 $a_i$，每次选择一个相连的点，每走一次到该点，该点的点权变为 $(a_i+1)\bmod k$。

可以从任意点开始，任意点结束，能重复经过多次。

问有多少个出发点，满足最后存在一种方案使得点权均为 $0$。

原题：$n\leq 2500,k=12$

加强版：$n\leq 2\times 10^6,k\leq 10^9$。

阅读全文 »