摘要
Title: 4729. 解密
Tag: 韦达定理、二分
Memory Limit: 64 MB
Time Limit: 1000 ms

4729. 解密

题意

给定一个正整数 k, 有 k次询问，每次给定三个正整数 ni,ei,di，求两个正整数 pi,qi，使 ni=pi×qi，ei×di=(pi−1)(qi−1)+1
思路

通过数学推导可以推出
p + q = m
p * q = n
那么可以通过两个方式求出
- 韦达定理
  即还原出原来的二元一次方程，然后通过求根公式判断是否有解，然后求解即可
- 二分
  可知p, q的上下限，可通过两个条件进行二分，最后验证两者相乘是否等于n即可

代码

韦达定理

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

int main()
{
    int k;
    scanf("%d", &k);

    while (k -- )
    {
        LL n, d, e;
        scanf("%lld%lld%lld", &n, &d, &e);
        LL m = n - e * d + 2;
        LL dt = m * m - 4 * n;
        LL r = sqrt(dt);

        if (dt < 0 || r * r != dt) puts("NO");
        else printf("%lld %lld\n", (m - r) / 2, (m + r) / 2);
    }

    return 0;
}

二分

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-28 10:45:38
* @FilePath: \Acwing\4729\4729.cpp
* @LastEditTime: 2023-01-28 10:56:17
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

signed main()
{
    IOS;
    int k, n, d, e;
    cin >> k;
    while (k--)
    {
        cin >> n >> d >> e;
        int m = n - e * d + 2;
        // p * q = n
        // p + q = m
        // 解一定是正整数
        // 找p
        int l = 1, r = m;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (mid * (m - mid) >= n)
                r = mid;
            else
                l = mid + 1;
        }
        if (l * (m - l) == n)
        {
            cout << l << " " << m - l << '\n';
        }
        else
            cout << "NO\n";
    }
    return 0;
}

4729. 解密

题意

思路

代码