「LOJ 138」类欧几里得算法

给出 $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$ 取模。

「CC SQRGOOD」Simplify the Square Root-杜教筛 + 二分

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

「LOJ 6053」简单的函数-ExtendedEratosthenesSieve

一个函数 $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$。

「SuperOJ 1297」数学题-ExtendedEratosthenesSieve

定义欧拉函数的变种
$$\phi(n, d) = \prod_{k = 1} ^ m (p_k ^ {e_k} + d)$$
特别的,$\phi(1, d) = 1$,求
$$\sum_{i = 1} ^ n \phi(i, d) \pmod {10 ^ 9 + 7}$$

「BZOJ 4916」神犇和蒟蒻-ExtendedEratosthenesSieve

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

「SPOJ DIVCNT[2/3/k]」-ExtendedEratosthenesSieve

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

Extended Eratosthenes Sieve

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

「BZOJ 5020」在美妙的数学王国中畅游-Link-Cut-Tree

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

「模拟测试」20171024

T1 建设图

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

「BZOJ 3453」XLkxc-拉格朗日插值


$$\sum_{i=0}^{n} \sum_{j=1}^{a+i \times d} \sum_{l=1}^{j}l^k$$

「BZOJ 4559」成绩比较-拉格朗日插值

$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$ 的余数就可以了。

「51NOD 1195」斐波那契数列的循环节-二次剩余

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

「BZOJ 4176」Lucas的数论-莫比乌斯反演+杜教筛


$$\sum_{i = 1} ^ n\sum_{j = 1} ^ nd(ij)$$

「BZOJ 3028」食物-生成函数

链接

BZOJ 3028

「BZOJ 2813」奇妙的 Fibonacci-线性筛

Fibonacci 数列是这样一个数列:
$F_1 = 1, F_2 = 2, F_3 = 3 \cdots$ $F_i = F_{i - 1} + F_{i - 2}$ (当 $i \geq 3$)
pty 忽然对这个古老的数列产生了浓厚的兴趣,他想知道:对于某一个 Fibonacci 数 $F_i$,有多少个 $F_j$ 能够整除 $F_i$ ($i$ 可以等于 $j$),他还想知道所有 $j$ 的平方之和是多少。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×