【题解】P8814 题解

liangbob · 2022-11-14 17:44:42 · 题解

P8814 题解

思路分析

这道题首先要知道和积原理。

然后，我们开始推式子。

移项可得 p_i + q_i = n_i - e_i \times d_i + 2，即 p_i + q_i 一定。根据和积原理，p_i+q_i 满足单调性。即可以使用二分查找枚举 p_i 进行计算。

注意：因为要求 p_i \leq q_i ，所以将 p_i 枚举到 \left\lfloor\\\dfrac{p_i+q_i}{2}\right\rfloor 即可。

代码

#include <iostream>
#include <cmath>
#define ll long long
using namespace std;

ll ef(ll l, ll r, ll n, ll m) //二分 
{
    while(l <= r)
    {
        ll mid = ((l + r) >> 1);
        ll cj = mid * (m - mid);//乘积
        if(cj == n)
        {
            return mid;
        }
        else
        {
            if(cj < n)//小于往大的枚举
            {
                l = mid + 1;
            }
            else // 大于往小的枚举
            {
                r = mid - 1;
            }
        }
    }
    return -1;//无解
}

int main()
{
    ll k;
    cin >> k;
    while(k--)
    {
        ll n, e, d;
        cin >> n >> e >> d;
        ll m = n - e * d + 2;//p+q的和
        ll q = ceil(m / 2);//p的枚举上限
        ll x = ef(1ll, q, n, m);
        if(x != -1) cout << x << " " << m - x << endl;
        else cout << "NO" << endl;
    }
    return 0;
}