题目描述
给定一个正整数 $k$,有 $k$ 次询问,每次给定三个正整数 $n_i, e_i, d_i$,求两个正整数 $p_i, q_i$,使 $n_i = p_i × q_i$,$e_i × d_i = (p_i − 1)(q_i − 1) + 1$。
输入格式
第一行一个正整数 $k$,表示有 $k$ 次询问。
接下来 $k$ 行,第 $i$ 行三个正整数 $n_i, d_i, e_i$。
输出格式
输出 $k$ 行,每行两个正整数 $p_i, q_i$ 表示答案。
为使输出统一,你应当保证 $p_i ≤ q_i$。
如果无解,请输出 NO
。
数据范围
以下记 $m = n − e × d + 2$。
保证对于 $100\\%$ 的数据,$1 ≤ k ≤ 10^5$,对于任意的 $1 ≤ i ≤ k$,$1 ≤ n_i ≤ 10^{18}$,$1 ≤ e_i × d_i ≤ 10^{18}$,$1 ≤ m ≤ 10^9$。
输入样例:
10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109
输出样例:
2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
解题思路
我们得到一个方程组:
$$
\begin {cases}
p _ i q _ i = n _ i & (1) \\\
(p _ i - 1) (q _ i - 1) + 1 = e _ i d _ i & (2)
\end {cases}
$$
由 $(2)$ 式展开得:
$$
p _ i q _ i - p _ i - q _ i + 2 = e _ i d _ i \tag 3
$$
由 $(1)$ 式减 $(3)$ 式得:
$$
p _ i + q _ i - 2 = n _ i - e _ i d _ i \\\
p _ i + q _ i = n _ i - e _ i d _ i + 2 \tag 4
$$
记 $m _ i$ 为 $n _ i - e _ i d _i + 2$,则由 $(4)$ 得:
$$
p _ i + q _ i = m _ i \tag 5
$$
联立 $(1) (5)$ 得:
$$
\begin {cases}
p _ i q _ i = n _ i \\\
p _ i + q _ i = m _ i
\end {cases}
$$
得到这个方程组后,我们可以直接求解二元二次方程(不过有时 sqrt ()
精度会挂),但作者采用的是二分法。
由这张函数图可知,当 $m _ i = 8$ 时,当 $p _ i = q _ i = \frac {m _ i} 2 = 4$ 时函数取最大值。并且在 $x \in [0, 4]$ 这一段函数是单调递增的。如果 $m _ i$ 是奇数,则 $p _ i = q _ i - 1 = \frac {m _ i - 1} 2$ 时函数取最大值(仅就整数而言)。于是,我们把二分域定为 $\big [0, \lfloor {m _ i \over 2} \rfloor \big]$。
二分时,若 $mid (m _ i - mid) \ge n _ i$(刚好或太大了),则 $r = mid$;否则 $l = mid + 1$。
最后令 $p _ i = l, q _ i = m _ i - l$。若 $p _ i q _ i = n _ i$,输出 $p _ i, q _ i$;否则输出 NO
。
AC Code
#include <cstdio>
using namespace std;
int T, m, l, r, mid;
long long n, a, b;
int main ()
{
scanf ("%d", &T);
while (T --)
{
scanf ("%lld%lld%lld", &n, &a, &b), m = n - a * b + 2;
l = 1, r = m >> 1;
while (l < r)
{
mid = l + r >> 1;
if ((long long) mid * (m - mid) >= n)
{
r = mid;
}
else
{
l = mid + 1;
}
}
if ((long long) l * (m - l) == n)
{
printf ("%d %d\n", l, m - l);
}
else
{
puts ("NO");
}
}
return 0;
}
感谢观看!
密码碎片:one
$$\href {/blog/content/29204/} {\color {Lime} {【寒假每日一题】题解}}$$
第五次:
AcWing【集日历瓜分10000AC币活动】赠送1月日历!
AcWing【集日历瓜分10000AC币活动】赠送2月日历!
AcWing【集日历瓜分10000AC币活动】赠送9月日历!
这是此题解最后一次了
不会的qwq,一月,二月
被感动了,虽然自己也没8,10
三月,四月
好我也来发:
AcWing【集日历瓜分10000AC币活动】赠送1月日历!
AcWing【集日历瓜分10000AC币活动】赠送2月日历!
AcWing【集日历瓜分10000AC币活动】赠送3月日历!
AcWing【集日历瓜分10000AC币活动】赠送4月日历!
AcWing【集日历瓜分10000AC币活动】赠送5月日历!
AcWing【集日历瓜分10000AC币活动】赠送9月日历!
AcWing【集日历瓜分10000AC币活动】赠送11月日历!
AcWing【集日历瓜分10000AC币活动】赠送12月日历!
预告:第五次将会发 $3$ 个。
第四次:
AcWing【集日历瓜分10000AC币活动】赠送1月日历!
第三次(先送张 $1$ 月):
AcWing【集日历瓜分10000AC币活动】赠送1月日历!
没抢到的朋友不用着急,明天还有
第二次:
AcWing【集日历瓜分10000AC币活动】赠送1月日历!
AcWing【集日历瓜分10000AC币活动】赠送8月日历!
AcWing【集日历瓜分10000AC币活动】赠送1月日历!
拿到的朋友记得帮忙点个赞啊
除夕之前发多一点,但会分时间发:(1-19-21点, 1-19-22点, 1-20-10点)
AcWing【集日历瓜分10000AC币活动】赠送1月日历!
AcWing【集日历瓜分10000AC币活动】赠送5月日历!
有多余的10月嘛大佬
😭
没有(悲)
da<0||xyxy!=da||(b-xy)%2
da>0&&xyxy==da&&(b-xy)%2==0;这两条判断语句第一个AC第二个一个也过不了
第 $4.5$ 次:
AcWing【集日历瓜分10000AC币活动】赠送1月日历!
大佬QWQ