zx2003说多 log 过不去，不然就去写了

Codeforces 1034D

题意

你有 $n$ 个区间 $[a_i, b_i]$，定义区间的区间 $[l,r]$ 的价值是第 $l$ 个区间到第 $r$ 个区间的并的总长度

你需要找出 $k$ 个不同的区间的区间，使得它们的总价值最大

输出总价值

$1\le n \le 3 * 10^5,1 \le k \le \min{\frac{n(n+1)}{2},10^9}$

为什么模数是偶数我都敢先取模后除以2了。不知道是不是傻了。

51nod 1965

题意

求

$$\prod_{i=1}^n \sigma_0(i)^{\mu(i)+i} \mod(10^{12}+39)$$

其中 $\sigma_0(i)$ 表示 $i$ 的正约数个数，$10^{12}+39$ 是质数

$n\le 10^{11}$

51nod 1847

题意

给出 $n,k$ 求

$$\sum_{i=1}^n\sum_{j=1}^n sgcd(i,j)^k$$

其中 $sgcd(i,j)$ 表示 $i,j$ 的次大公约数，特殊地，$sgcd(1,1)=0$

对 $2^{32}$ 取模

$n\le 10^9, k\le 50$

SPOJ APS2

题意

令 $f(i)$ 表示 $i$ 的最小质因子

求 $$\sum_{i=2}^n f(i)$$

$n\le 1.234567891011*10^{12}$

问题

有 $n$ 个物品，每个物品有两个属性 $a_i$ 和 $b_i$，需要选出 $k$ 个，设选出的编号集合是 $S$。

最大化

$$\frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i}$$

保留一定精度。

题意

令 $\sigma_0(n)$ 表示 $n$ 的约数个数

求 $$\sum_{i=1}^n \sigma_0(i^3)$$

$n\le 10^{11}$

题意

令 $\sigma_0(n)$ 表示 $n$ 的约数个数

求 $$\sum_{i=1}^n \sigma_0(i^2)$$

$n\le 10^{12}$

前言

大家都会啊，还是一次考试题的部分分，听 ftq 讲了

咕了几天就来学了

好像比杜教筛少很多思维难度吧

update:

好难啊，重新理解了好多次，还改了文章结构

简介

如果一个积性函数 $f(i)$ 在 $i$ 是质数时是一个关于 $i$ 的低次多项式，并且在质数的幂处的能快速求，那么大概可以用Min_25筛来求

$$\sum_{i=1}^n f(i)$$

对于 $f(1)$ 特判

时间复杂度 $\mathcal O(\frac{n^\frac{3}{4}}{\log n})$，空间复杂度$\mathcal O(\sqrt{n})$

并且同时我们可以求出每个 $\lfloor \frac{n}{x} \rfloor$ 的 $\sum\limits_{i=2}^{\lfloor \frac{n}{x} \rfloor}[\text{$i$ 是质数}]f(i)$

H. Playing games

题意

你有 $n$ 堆石子，数量分别是 $a_1,..,a_n$

问最多能选出几堆使得玩 Nim游戏 满足后手必胜

$n,a_i\le 5*10^5$

没有思维能力了

Codeforces 1034C

题意

给你一棵 $n$ 个点的树，有点权$a_1,..,a_n$，整棵树是一个1级区域

• 除非 $i$ 是最后一个等级，否则每一个i级区域都要被分成至少两个i+1级区域

• 每个点必须恰好属于一个每种等级的区域

• 一个区域必须是连通的

• 每个相同等级的区域必须拥有相同的点权和

求有多少种不同的划分方案，模 $10^9+7$

$n\le 10^6,a_i\le 10^9$