Volume 11

501. Eight Divisors

令表示小于等于的素数个数, 那么

计算可以参考Prime-counting function.

502. Counting Castles

503. Compromise or persist

504. Square on the Inside

根据pick定理, 暴力枚举之后可以方便算出内部格点数目, 然后统计下就好了.

505. Bidirectional Recurrence

506. Clock sequence

507. Shortest Lattice Vector

508. Integers in base

509. Divisor Nim

打表下就可以发现等于在二进制下末尾的个数, 枚举, 那么很容易计算出满足. 然后答案就是.

510. Tangent Circles

根据Descartes' theorem可以很容易算出的值. 然后稍微化简下可以知道. 枚举就好了.

511. Sequences with nice divisibility properties

显然是的约数, 考虑表示对取模是的方案数, 转移方程很显然, 然后利用的线性递推做就好了.

512. Sums of totients of powers

显然, 于是. 令, 那么就有, 直接递归计算就好了.

513. Integral median

可以知道这个公式, 令, 得到, 也就是求, 限制条件有

移项化简得到, 不妨令, 那么有

令, 那么. 可以用Stern-Brocot Tree枚举, 然后枚举, 根据上面的不等式可以算出的范围. 这样直接暴力可以在1分钟内出解了. 注意到, 实际上就是枚举了所有的, 因此可以考虑直接枚举然后用openmp加速, 大概可能很快出解.

514. Geoboard Shapes

515. Dissonant Numbers

516. -smooth totients

令, 显然如果, 那么且只包含这三个质因子. 于是可以枚举出所有的, 然后再dfs一遍计算答案就好了.

517. A real recursion

518. Prime triples and geometric sequences

化简一下可以得到, 然后枚举就好了.

519. Tricolored Coin Fountains

520. Simbers

521. Smallest prime factor

522. Hilbert's Blackout

523. First Sort I

可以很明显第发现, 如果第前面有数比它小, 那么需要调整次才能排好这个位置. 于是枚举算下方案数就好了.

524. First Sort II

525. Rolling Ellipse

526. Largest prime factors of consecutive numbers

527. Randomized Binary Search

528. Constrained Sums

529. -substrings

530. GCD of Divisors

531. Chinese leftovers

枚举和, 然后用同余方程合并解决就好了.

532. Nanobots on Geodesics

533. Minimum values of the Carmichael function

534. Weak Queens

535. Fractal Sequence

536. Modulo power identity

537. Counting tuples

538. Maximum quadrilaterals

539. Odd elimination

540. Counting primitive Pythagorean triples

我们知道互素勾股数对的这个公式, , 其中. 根据这个公式, 这个题有了很多计数的方法.

方法一

考虑枚举 , 那么如果是偶数, 只需要计算集合的大小. 如果是奇数, 那么只需要计算集合的大小.

问题变成给出一个和, 问区间内有多少数和互质. 这个可以容斥做, 考虑的质因数集合, 那么答案显然就是.

方法二

令

如果定义

方法三

令

541. Divisibility of Harmonic Number Denominators

542. Geometric Progression with Maximum Sum

543. Prime-Sum Numbers

根据哥德巴赫猜想, 所有大于2的奇数都可以表示成2个素数的和. 于是答案可以分成4部分:

1. , 显然是素数, 于是答案是.

2. , 是一个奇数, 如果那么答案是, 否则答案是.

3. , 是一个偶数并且, 那么不能超过, 答案是.

4. , 是一个奇数且, 那么最大能到, 于是答案是.

前两种可以直接算, 后两种就等差数列求个和好了.

544. Chromatic Conundrum

545. Faulhaber's Formulas

可以知道就是第个伯努利数的分母. 第个伯努利数的分母可以这么计算出来: . 然后通过简单的计算可以知道, 也就是说. 同样我们知道如果某个不满足条件, 那么也是不满足条件的. 于是我们可以用筛法来求出所有可行的.

546. The Floor's Revenge

547. Distance of random points within hollow square laminae

从边长为和的矩形中选两个点, 距离期望公式如下:

548. Gozinta Chains

很容易写出递推式, 显然如果令, 答案之和构成的集合有关, 于是可以先生成每个集合, 并且算出每个集合对应的答案. 然后考虑每个的质因数分解, 如果指数部分构成的集合和相同, 那么就是一个合法的.

549. Divisibility of factorials

考虑, 那么只要整除每个就好了, 这个可以二分答案确定, 对所有的取最大的就是的值.

550. Divisor game

可以暴力算出每个, 然后可以观察到的最大值不超过, 于是就可以直接矩阵乘法搞了. 也可以用fwt做异或卷积.