25暑期1
Problem E
\(T\) 组询问，给两个数 \(a,b\)，询问 \(|a^2-b^2|\) 的值在集合 \(C\) 中为第几小，\(C=\{|x^2-y^2|\mid x,y\in N^*,x\not=y\}\)。例如 \(3,5,7,8,9\in C\)，且为前五小。
\(1≤T≤10^4,1≤a,b≤10^9,a\not=b\)。
点击查看题解
设 \(a>b\)。\(a^2-b^2=(a+b)(a-b)\)。则 \(a+b\) 和 \(a-b\) 同奇偶。可推出 \(a^2-b^2\bmod 4 \not=2\)。
又 \(\forall\text{ }m_1\ge 1,\exists\text{ }x_1,y_1\in N^*\)，满足 \(x_1-y_1=m_1\)； \(\forall\text{ }m_2\ge 3,\exists\text{ }x_2,y_2\in N^*\)，满足 \(x_2+y_2=m_2\)。
则 \(C=\{n\mid n\ge3,n\not=4,n\bmod4\not=2\}\)。据此可计算排名。
1 |
|
