给出 $T$ 组询问，每组用 $n, a, b, c, k_1, k_2$ 来描述。对于每组询问，请你求出

$$
\sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2}
$$

对 $1000000007$ 取模。

求第 $n$ 个含有大于 $1$ 的平方因子的数。

一个函数 $f(x)$，它满足：

1. $f(1) = 1$。
2. $f(p ^ c) = p \oplus c$（$p$ 为质数，$\oplus$ 表示异或）。
3. $f(ab) = f(a)f(b)$（$a$ 与 $b$ 互质）。

求 $\sum\limits_{i = 1} ^ n f(i) \bmod 1000000007$。

定义欧拉函数的变种

特别的，$\phi(1, d) = 1$，求

求 $A = \sum\limits_{i = 1} ^ n \mu(i ^ 2), B = \sum\limits_{i = 1} ^ n \varphi(i ^ 2)$

求 $\sum\limits_{i = 1} ^ n \sigma_{0}(i ^ k)$，$n, k \leq 10 ^ {10}, T \leq 10000$。

扩展埃拉托色尼筛法可以在大约 $O(n ^ {\frac {2} {3}})$ （这里以实际运行效果估计，实际复杂度据说和洲阁筛一样）求出一般积性函数的前缀和，消耗 $O(\sqrt{n})$ 的空间。

维护一个森林，每个点有一个函数 $f$，要求支持连接两个点，断开两个点，修改某个点的函数，询问路径上函数 $f(x)$ 的和。

T1 建设图

给出一个无向图，求最少添加多少条边使得，无论删掉哪条边任意两点都可以互相到达。

求

$G$ 系共有 $n$ 位同学，$M$ 门必修课。这 $N$ 位同学的编号为 $0$ 到 $N - 1$ 的整数，其中 $B$ 神的编号为 $0$号。这 $M$ 门必修课编号为 $0$ 到 $M - 1$ 的整数。一位同学在必修课上可以获得的分数是 $1$ 到 $U_i$ 中的一个整数。如果在每门课上 $A$ 获得的成绩均小于等于 $B$ 获得的成绩，则称 $A$ 被 $B$ 碾压。在 $B$ 神的说法中，$G$ 系共有 $K$ 位同学被他碾压（不包括他自己），而其他 $N-K-1$ 位同学则没有被他碾压。$D$ 神查到了 $B$ 神每门必修课的排名。这里的排名是指：如果 $B$ 神某门课的排名为 $R$，则表示有且仅有 $R-1$ 位同学这门课的分数大于 $B$ 神的分数，有且仅有 $N-R$ 位同学这门课的分数小于等于 $B$ 神（不包括他自己）。我们需要求出全系所有同学每门必修课得分的情况数，使其既能满足B神的说法，也能符合 $D$ 神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。你不需要像 $D$ 神那么厉害，你只需要计算出情况数模 $10 ^ 9 + 7$ 的余数就可以了。

求斐波那契数列 $\text{mod }n$ 的循环节长度。

求

链接

BZOJ 3028

链接

UOJ 221
BZOJ 4652
LOJ 2085

Fibonacci 数列是这样一个数列：

pty 忽然对这个古老的数列产生了浓厚的兴趣，他想知道：对于某一个 Fibonacci 数 $F_i$，有多少个 $F_j$ 能够整除 $F_i$ ($i$ 可以等于 $j$)，他还想知道所有 $j$ 的平方之和是多少。