[CSP-J 2022 T2] 解密
题目描述：给定一个正整数 k，有 k 次询问，每次给定三个正整数 ni,ei,di，求两个正整数 pi,qi，使 ni=pi×qi、ei×di=(pi−1)(qi−1)+1。
首先把两个公式转化成关于p的一元二次方程来求解。然后判断整数解是否能满足原方程。
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long k, n, e, d, m, t;
long long p1, p2, q1, q2;
long long ap, aq, tmp;
bool flag;
for (scanf("%lld", &k); k; k--)
{
scanf("%lld%lld%lld", &n, &d, &e);
flag = true;
m = n - e * d + 2; //数据范围中说明m>=1的整数
if (m * m - 4 * n >= 0)
{
t = sqrt(m * m - 4 * n);
p1 = (m - t) / 2;
p2 = (m + t) / 2;
q1 = n / p1;
q2 = n / p2;
if (n == p1 * q1 && e * d == (p1 - 1) * (q1 - 1) + 1)
{
ap = p1;
aq = q1;
if (ap > aq)
tmp = ap, ap = aq, aq = tmp;
}
else if (n == p2 * q2 && e * d == (p2 - 1) * (q2 - 1) + 1)
{
ap = p2;
aq = q2;
if (ap > aq)
tmp = ap, ap = aq, aq = tmp;
}
else
flag = false;
}
else
{
flag = false;
}
if (flag == false)
printf("NO\n");
else
printf("%lld %lld\n", ap, aq);
}
return 0;
}也可以用函数来做。原理一样。
#include <bits/stdc++.h>
using namespace std;
bool dec(long long n, long long d, long long e, long long *p, long long *q);
int main()
{
long long k, n, d, e, p, q;
bool flag;
cin >> k;
while (k--)
{
cin >> n >> d >> e;
flag = dec(n, d, e, &p, &q);
if (flag)
cout << p << ' ' << q;
else
cout << "NO";
cout << endl;
}
return 0;
}
bool dec(long long n, long long d, long long e, long long *p, long long *q)
{
long long delt = (e * d - n - 2) * (e * d - n - 2) - 4 * n;
long long t = sqrt(delt);
long long x1, x2;
long long p1, q1;
if (delt < 0 || t * t != delt)
return false;
x1 = n + 2 - e * d - t;
x2 = n + 2 - e * d + t;
if (x1 % 2 || x2 % 2)
return false;
*p = x1 / 2;
*q = x2 / 2;
p1 = x1 / 2;
q1 = x2 / 2;
if (n == p1 * q1 && e * d == (p1 - 1) * (q1 - 1) + 1)
return true;
else
return false;
}