午夜久久一区,东京热av电影网,911污视频

Link 1

Link 2

Link 3

Link 4

Link 5

看不懂

261

319

465

367
492
251
276

394
503
360
245

388
513
273
447

302
518
379
508

369
550
499

Solutions

題號標 x 的需要看證明 / 重新思考 / 寫代碼

Problem 110 Diophantine reciprocals II

在如下方程中， $x,y,n$ ，均為正整數(shù)（其中 $x \le y$ ）
$\frac 1 x + \frac 1 y = \frac 1 n$
不同的解的總數(shù)超過四百萬種的最小 $n$ 值是多少？

Solution

此題有一個優(yōu)美的結(jié)論：此方程組的解數(shù)為 $\frac {d(n^2) + 1} 2$

proof

考慮 $b = \frac {an} {a-n}$ 是整數(shù)，又由于 $an - n(a-n) = n ^2 \ \Longrightarrow \ \gcd(an,a-n) \mid n^2$

$\gcd (an, a-n) = a-n$ ，得到 $a - n \mid n^2$ 。那么令 $a = n + t$ ， $t$ 就是 $n^2$ 的一個約數(shù)，易得這是一個充要條件

令 $n = 2^{p_1} 3 ^{p_2} 5^{p_3}$ ，注意到 $d(n^2) = \prod (2p_i + 1)$ ，那么最優(yōu)解一定有 $p_1 \ge p_2 \ge \cdots$ ，以此作為剪枝即可。

參考資料

Problem 233x Lattice points on a circle

作過點 $(0,0)$ 、 $(N,0)$ 、 $(0,N)$ 和 $(N,N)$ 的圓，記圓周上坐標為整數(shù)的點的數(shù)目為 $f(N)$ 。

有些正整數(shù) $N?\le?10^{11}$ 且 $f(N)?=?420$ ，這些正整數(shù)的和是多少？

Solution

考慮到 $n^2$ 需要表示為兩個數(shù)的平方和。這里有 費馬平方和定理

一個奇質(zhì)數(shù)能表示為兩個數(shù)的平方和的充要條件是
$p \equiv 3 \pmod 4$

根據(jù)經(jīng)典恒等式 $(a^2 + b^2)(c^2 + d^2) = (ac+bd)^2 + (ad-bc)^2$ ，可以得到：這種質(zhì)數(shù)的乘積也能表示為兩個平方數(shù)的和。
分解 $\frac {420} 4 = 105$ 后討論，最后轉(zhuǎn)化為一個線性篩DP（考慮每個這種質(zhì)數(shù)的指數(shù)）

參考資料

Note 事實上，任意一個 $4k+1$ 素數(shù)都能 唯一的 表示為兩個數(shù)的平方和。這是因為 高斯整數(shù)環(huán) 是一個歐氏環(huán)，滿足唯一分解性，具體參見高代書的內(nèi)容

Problem 271 Modular Cubes, part 1

對于正整數(shù) $n$ ，存在整數(shù) $x$ ，滿足 $1<x<n$ ，且 $x^3 \equiv 1 \pmod n$ 。記所有這樣的整數(shù) $x$ 的和為 $S(n)$ 。

求 $S(13082761331670030)$ 。

Solution

注意到將模數(shù)分解后，每個質(zhì)因子獨立（這些質(zhì)因子都很?。?，于是求出每一個質(zhì)因子下的三次剩余，暴力 CRT 合并即可

Problem 272x Modular Cubes, part 2

對于正整數(shù) $n$ ，存在整數(shù) $x$ ，滿足 $1<x<n$ ，且 $x^3 \equiv 1 \pmod n$ 。記所有這樣的整數(shù) $x$ 數(shù)目為 $C(n)$ 。

對于所有使得 $C(n)=242$ 的正整數(shù) $n \le 10^{11}$ ，求它們的和。

Solution

考慮三次剩余的性質(zhì)，并注意到 $253=3^5$ （實際上一定是3的冪次）

三次剩余的性質(zhì)：
$\begin{split} d(p) &= 1 \\ d(p^n) &= 3 \\ d(p^n) &= 3 \quad\quad p \equiv 1 \pmod 3 \\ d(p^n) &= 1 \quad\quad p \equiv 2 \pmod 3 \\ \end{split}$

參考資料 1

參考資料 2

參考資料 3

Problem 292 Pythagorean Polygons

我們定義 畢達哥拉斯多邊形 為滿足下列性質(zhì)的凸多邊形：

有至少三個頂點，

不存在三個頂點共線，

每個頂點坐標均為整數(shù)，

每條邊長度均為整數(shù)。

對于給定的整數(shù) $n$ ，記 $P(n)$ 為邊長 $\le?n$ 的不同畢達哥拉斯多邊形的數(shù)目。
只要不能將其中一個通過平移得到另一個，就被認為是不同的畢達哥拉斯多邊形。

求 $P(120)$ 。

Solution

顯然可以得到一個DP做法，利用畢達哥拉斯三元組轉(zhuǎn)移。

注意到條件 不存在三個頂點共線，于是考慮本原畢達哥拉斯三元組，所有三元組都可以由這個東西生成，于是用這個東西轉(zhuǎn)移即可，由于斜率的單調(diào)性，可以前綴和優(yōu)化一下

Problem 295 Lenticular holes

若兩圓重疊而成的凸區(qū)域滿足以下條件，我們稱之為 透鏡孔洞

兩圓的中心都是格點。

兩圓在兩個格點處相交。

兩圓重疊而成的凸區(qū)域內(nèi)部不包含任何格點。

如果存在兩個半徑分別為 $r_1$ 和 $r_2$ 的圓能夠生成透鏡孔洞，我們就稱有序正實數(shù)對 $(r_1, r_2)$ 為透鏡數(shù)對。

記 $L(N)$ 是所有滿足 $0<r1\le r2 \le N$ 的不同透鏡數(shù)對的數(shù)目。

求 $L(100 000)$ 。

Solution

通過 不等式 得到了長度的上界?？紤]其中垂線，根據(jù)限制，是一段區(qū)間， $\gcd$ 即可

Problem 341 The Mouse on the Moon

考慮一個 $500 \times 500$ 的網(wǎng)格，中心有一個半徑為 $250$ 的網(wǎng)格，要求選擇一個多邊形，與圓不相交（可以相切），并且頂點都在整點上，求包圍面積與周長的最大比值。

[站外圖片上傳中...(image-71e329-1535885869188)]

Solution

分數(shù)規(guī)劃好題！

二分答案，觀察到一條邊的貢獻，可以由叉積減去答案乘長度得到，利用凸多邊形的性質(zhì)，按照 $x$ 排序，DP 即可

Problem 362x Squarefree factors

我們記 $F_{sf}(n)$ 是將 $n$ 分解為一個或多個大于 $1$ 的無平方因子因數(shù)乘積的方式數(shù)。

記 $S(n)$ 為 $\sum _{k=1} ^{n} F_{sf}(k)$ 。求 $S(10^{10})$ 。

Solution

首先線性篩出無平方因子數(shù)，考慮暴力DP， $f(i,j)$ 考慮 $[1,i]$ 中，用不超過 $p[j]$ 無平方因子數(shù)表出的個數(shù)。
然而這樣暴力大概是 $O(n \sqrt n)$ 的。

注意到我們只需要考慮到根號級別的質(zhì)數(shù)（因為大于根號的至多只有一個），其他的前綴和算一算，復(fù)雜度就是 $O(n)$ 的了

Problem 373 Circumscribed Circles

每個三角形都有一個經(jīng)過三個頂點的外接圓?？紤]所有外接圓半徑也是整數(shù)的整數(shù)邊長三角形。

取其中外接圓半徑不超過 $n$ 的三角形，記它們的外接圓半徑之和為 $S(n)$ 。

求 $S(10^7)$ 。

Solution

通過××可以發(fā)現(xiàn)，一個結(jié)論：這種三角形的三邊，一定是畢達哥拉斯三元組的直角邊。

proof

考慮一個三角形 $ABC$ ，他的圓心為 $O$ ?？紤]作過 $A$ 的直徑 $AD$ ，連 $AD, BD$ 。

根據(jù)托勒密定理，有：
$a \sqrt {4r^2 - b^2} + b \sqrt {4r^2 - a^2} = 2rc$
于是根號下的東西是完全平方數(shù)。

由于小于 $n$ 的畢達哥拉斯三元組是 $O(n)$ 級別的，所以暴力生成三元組，枚舉半徑， $a,b$ ，求出 $c$ ，即可。

Note 似乎存在規(guī)律：兩個 $r_1, r_2$ ，如果它們的分解當(dāng)中 $4k+1$ 素數(shù)的指數(shù)分布相同，它們的答案相同。（如何證明？）

Problem 416 A frog’s trip

在一列 $n$ 個方塊的最左邊一個上有一只青蛙。青蛙通過連續(xù)不斷的跳躍，先跳到最右邊的方塊，然后再跳回最左邊的方塊。它向右跳的時候每次可以跳一個、兩個或三個方塊，跳回來時也同理。它不能跳出這些方塊。這樣的往返它一共進行了 $m$ 次。

記 $F(m, n)$ 為青蛙在旅途中至多有一個方塊從未被跳到過的方式總數(shù)。

求 $F(10, 10^{12})$ 的最后 $9$ 位數(shù)字。

Solution

把從右向左跳的青蛙反轉(zhuǎn)方向，所有 $20$ 只一起考慮，可以矩陣快速冪解決。

狀態(tài)只需維護兩個位置的青蛙數(shù)量，剩下一個可以直接得到。

Hardest

Problem 446 Retractions B*

對于任意整數(shù) $n>1$ ，函數(shù)族 $f_{n,a,b}$ 按如下方式定義： $f_{n,a,b}(x) \equiv ax+b \pmod n$ ，其中 $a,b,x$ 都是整數(shù)，且 $0<a<n，0 \le b<n，0 \le x<n$ 。

我們稱 $f_{n,a,b}$ 為撤銷函數(shù)，當(dāng) $0\le x<n$ 均有在模 $n$ 意義下 $f_{n,a,b}(f_{n,a,b}(x)) \equiv f_{n,a,b}(x)$ 。

記 $R(n)$ 是給定 $n$ 下撤銷函數(shù)的數(shù)目。記 $F(N)=\sum R(n^4+4)$ ，其中 $1 \le n \le N$ 。

求 $F(10 ^7) \pmod {1 000 000 007}$

Solution

首先可以證明一個結(jié)論：
$R(n) = \prod (p_i^{k_i} + 1) - n, \quad \quad n= p_1^{k_1} p_2^{k_2} p_3^{k_3} \cdots$

proof

考慮 $a(ax+b)+b \equiv ax + b \pmod n$ 等價于 $a(a-1)x+ab \equiv 0 \pmod n$ 。

令 $x$ 分別等于 $0, 1$ ，容易得到 $n \mid a(a-1)$ 并且 $n \mid ab$ ，顯而易見，這是個充分必要條件。

令 $d = \gcd(a, n)$ ，那么有 $b$ 存在 $d$ 種取值（ $b$ 是 $\frac n d$ 的倍數(shù)），并且 $\frac n d \mid a - 1$ 。

注意到 $x \cdot \frac n d + 1 = a = y \cdot d$ ，根據(jù)擴歐，容易得到：當(dāng)且僅當(dāng) $\gcd(d, \frac n d) = 1$ 時，存在解 $a$ ，并且解唯一（同時存在 $d$ 種解 $b$ ）

于是有
$R(n) = \sum _{d\mid n, \gcd(d, n/d) = 1} d - n = \prod (p_k^{k_i}+1) - n$

回到原問題。一個重要的事實是 $n^4 + 4 = ((n-1)^2 + 1)((n+1)^2 + 1)$ ，于是我們只需要考慮形如 $m^2 + 1$ 數(shù)的答案。

還有一個亟待解決的問題是 $((n-1)^2 + 1)$ 與 $((n+1)^2 + 1)$ 之間的公因子。
$\gcd((n-1)^2 + 1, (n+1)^2 + 1) = \gcd(n^2-2n+2, 4n)$
顯然當(dāng) $n$ 為偶數(shù)時，會存在公因子 $2$ ，而沒有公因子 $4$ 。

又 $n^2-2n+2 \equiv 2 \pmod n$ ，考慮 $n$ 大于 $2$ 的因子 $u$ ，則必定有 $u \not \mid n^2-2n+2$ 。

因而 $n$ 為偶數(shù)時， $\gcd$ 為 $2$ ，否則 $\gcd$ 為 $1$ 。

接下來，我們考慮使用篩法來求出所有的 $R(m^2 + 1)$ 。在這里，推薦 ZhouYuChen 的高效篩法，復(fù)雜度可以做到 $O(n \log \log n + n \log n)$ （由于去除的質(zhì)因子非常大，所以實際非常不滿）。

注意到 $m^2 \equiv -1 \pmod p$ ，在模 $p$ 意義下至多存在兩個解 $m_0, p-m_0$ ，逐個去篩 $kp-m_0, kp+m_0$ 即可。但是，如何說明處理到第 $i$ 個數(shù)時，剩下的 $n$ 為質(zhì)數(shù)？

proof

假設(shè)當(dāng)前去篩的數(shù)為 $n = p_1 p_2 \cdots$ ，任取兩個質(zhì)因子 $p, q\ (p \le q)$ 。

需要說明的是， $n$ 不存在平方因子。因為 $n \mid m^2 + 1$ ，而顯然 $m^2 + 1$ 不被任何質(zhì)數(shù)的平方整除?？梢缘玫? $p < q$

于是有
$m^2 + 1 \equiv 0 \pmod p \\ m^2 + 1 \equiv 0 \pmod q$

注意到，此時必定有 $m < \frac p 2$ ，也即 $m^2 + 1 \le \frac {p^2} 4$

假設(shè)
$m^2 + 1 = ap \quad (a \ge 1) \\ m^2 + 1 = bq \quad (b \ge 1)$
可以得到 $ap = bq$ ，根據(jù) $\gcd(p, q) = 1$ ，那么有 $a \ge q$ 。得到 $m^2 + 1 \ge pq$ ，與上述式子矛盾！