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// 解一定是正整数// 找pint l = 1, r = m;while (l < r){int mid = l + r >> 1;if (mid * (m - mid) >= n)r = mid;elsel = mid + 1;}if (l * (m - l) == n){cout << l << " " << m - l << '\n';}elsecout << "NO\n";}return 0;
}