数学水题

自己的数学基础简直烂到爆。。

从这里面随机做

113C. Double Happiness

问区间\([l, r]\)内有多少个素数可以表示为\(a^2 + b^2\)的形式

任何一个满足条件的数都可以表示为\(4k + 1\)的形式

证明

bitset压一下位

此题完结

代码

121C. Lucky Permutation

长度为\(n\)的排列中第\(k\)大的排列，有多少个位置满足下标和值都只含4/7

由于阶乘的数量增长非常迅速，而\(k\)又非常小，那么显然最后的序列只有最后几位会发生改变。

前面的位置都是\(i = a[i]\)。那么前面的可以直接数位dp/爆搜，后面的部分是经典问题，可以用逆康托展开计算。

代码

134B. Pairs of Numbers

数对\((a, b)\)每次可以变为\((a, a + b)\)或者\((a+b, a)\)(初始时为\((1, 1)\))，问其中一个变\(n\)的最小步数是多少

一个显然的思路是对所有\((N, i)\)算出答案后取个min，而对于任意\((N, i)\)最优的策略为变为\((N - i, i) -> (N - i - i, i)\)，然后不断递归下去

代码

294C. Shaass and Lights

给一串\(n\)个灯，有\(m\)个灯初始是亮的，并给出初始亮的灯的序号。每次操作能点亮靠近亮的灯的一盏灭的灯，问点亮所有的灯有多少种方案。

点亮所有的灯总共需要\(n - m\)次

对于每一段分别考虑，最左边和最右边的一段显然只有一种答案，中间的有\(2^{a_i - a_{i - 1} - 1}\)种答案

而对于每一段，我们还需要统计出其在答案序列中的出现情况，也就是\(C_{n - m - (sum_i)}^{a_i - a_{i - 1} - 1}\)

其中\(sum_i = \sum_{i = 1}^{i - 1} a_i - a_{i - 1} - 1\)

乘起来就是答案

代码

615D. Multipliers

给出一个数的质因子分解的形式，问其所有约数的积是多少，

直接枚举每个质因子的幂算贡献，注意指数取模要模\(\phi(10^9 + 7)\)

代码

616E. Sum of Remainders

求\(\sum_{i = 1}^m n \% i\)，\(1 \leqslant n, m \leqslant 10^{13}\)

\(n \% i = n - n / i * i\)

直接数论分块

代码

839D. Winter is here

给出一些数，求取出一些数，当他们的GCD大于0时，将数量乘GCD累加到答案上，求累加和。

枚举\(gcd\)，然后直接容斥减掉是\(gcd\)倍数的贡献

中途可能用到一点组合数的结论：\(\sum_{i = 1}^n i C_n^i = i * 2^{n - 1}\)

代码

448E. Divisors

给出一个x,k，每次操作都会将x分解因数，得到新的序列，然后每次再分解序列中的每一个数，按照每一个数分解因数从小到大排，整体顺序不做调整。

写了一发暴力居然过了。。

代码