Volume 10

451. Modular inverses

这题就是求的最大. 和#407一样, 一个方法就是枚举, 然后枚举的约数, 用更新.

考虑, 那么有. 对于某个, 有两个解和. 于是枚举, 将其质因数分解, 然后枚举每个质数取哪个解, 用中国剩余定理合并即可.

452. Long Products

453. Lattice Quadrilaterals

454. Diophantine reciprocals III

455. Powers With Trailing Digits

456. Triangles containing the origin II

457. A polynomial modulo the square of a prime

458. Permutations of Project

表示前个字符, 最后个字符的状态是的方案数, 这个状态可以用最小表示来搞, 总共只有种状态. 于是找出转移矩阵, 用快速幂即可.

459. Flipping game

460. An ant on the move

461. Almost Pi

用折半搜索的方法, 先枚举得出一些数, 然后枚举和, 在之前的数中二分即可.

462. Permutation of -smooth numbers

463. A weird recurrence relation

464. Möbius function and intervals

465. Polar polygons

466. Distinct terms in a multiplication table

467. Superinteger

468. Smooth divisors of binomial coefficients

469. Empty chairs

470. Super Ramvok

471. Triangle inscribed in ellipse

472. Comfortable Distance II

473. Phigital number base

474. Last digits of divisors

475. Music festival

476. Circle Packing II

477. Number Sequence Game

478. Mixtures

479. Roots on the Rise

根据三次方程的韦达定理, 可以知道, 然后等比数列直接算就好了.

480. The Last Question

481. Chef Showdown

482. The incenter of a triangle

483. Repeated permutation

484. Arithmetic Derivative

485. Maximum number of divisors

先线性筛求出所有, 然后用单调队列求一个窗口内的最值.

486. Palindrome-containing strings

487. Sums of power sums

488. Unbalanced Nim

489. Common factors between two sequences

490. Jumping frog

491. Double pandigital number divisible by

表示前位, 对取模结果是, 当前使用的数字状态为的方案数, 随便转移一下就好了.

492. Exploding sequence

493. Under The Rainbow

可以知道总的方案数是, 没有超过long long, 于是可以把分子直接计算出来. 计算就是一个很朴素的dp, 这里不表.

494. Collatz prefix families

495. Writing as the product of distinct positive integers

496. Incenter and circumcenter of triangle

497. Drunken Tower of Hanoi

498. Remainder of polynomial division

499. St. Petersburg Lottery

500. Problem

首先预处理出一些素数来. 显然, 每个素数的幂次都是的幂次. 于是考虑用优先队列来扩展, 每次取出最小的, 然后把放回去. 前个的乘积就是答案.