[CSP-J 2022] 解密

没想到吧，我今天居然会一点更新两篇博客，这题是我最伤心的一题，由于文件存错了导致爆零退役

题目传送门

题目描述

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

输入格式

第一行一个正整数 k，表示有 k 次询问。

接下来 kk 行，第 ii 行三个正整数 ni​,di​,ei​。

输出格式

输出 k 行，每行两个正整数 pi​,qi​ 表示答案。

为使输出统一，你应当保证 pi​≤qi​。

如果无解，请输出 NO。

输入输出样例

输入 #1

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

输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

分析

这题巨佬一眼就看出来是解一元二次方程，然而蒟蒻在考场竟一点也没往那方面想，直接用的二分答案

先讲一下不知道解方程的思路

建议先点传送门去看一下数据范围

看了数据范围之后我们又可以得到一个提示，可以把m求出来，从而用p表示q（反过来也一样）

可二分性

数形结合是一个很重要的思想，我们现在想象有一个矩形（长方形），长宽之和是知道的，求这个矩形的面积

随便的列举了几个数之后，我们会发现，这个矩形越接近正方形，所得的面积就越大

同理我们就可以推出p（q）的值是可二分的

AC代码

#include 
using namespace std;
long long m,n;
int check(int x){//二分其中一个难点就是check函数
	if(x * (m - x) == n) return 0;
	if(x * (m - x) < n) return 1;
	if(x * (m - x) > n) return 2;
}//自行体会吧
int main(){
	//freopen("decode.in","r",stdin);
	//freopen("decode.out","w",stdout);
	int k;
	cin >> k;
	while(k--){
		long long  e, d,p=0,q=0;
		scanf("%lld%lld%lld",&n,&e,&d);
		//cin >> n >> e >> d;
		m = n - e*d + 2;
		int l = 0, r = m;
		while(l < r){
			int mid = (l + r) >> 1;
			if(!check(mid)){
				if(mid > m - mid){
					p = (m - mid),q = mid;
				}else{
					p = mid;
					q = (m-mid);
				}//保证p小于q
				printf("%lld %lld\n",p,q);
				//cout << p << " " << q << endl;
				break;
			}else if(check(mid)== 1){
				l = mid+1;
			}else{
				r = mid;
			}
		}
		if(!p && !q){//注意这里一定要用且！因为在答案中有可能p等于0，只有当p q都是0的时候才是没找到答案
			printf("NO\n");
			//cout << "NO" << endl;
		}
	}
	return 0;
}

提示

二分中的难点是check函数，最烦的地方是边界值的问题，建议在二分还不熟练的时候，写好的代码一定要带特殊值去手模一下，看一下有没有可能死循环了

关于一元二次方程

既然这里涉及到了，那也就顺便科普一下吧，这是九上的知识了，解一元二次方程有一个最简单粗暴的方法：求根公式

设方程为：ax^2 + bx + c = 0 （a,b,c均为常数）

求根公式

求根公式具体怎么得到的我就不讲解了，反正可以用配方法推出来（如果有想知道的可以评论，我会具体写一篇博客讲解有关解一元二次方程）

x1,x2 = (-b ± √(b^2 - 4ac) ) / 2a

 顺便提一下，根号内的b^2-4ac一般用△表示，这也称作根的判别式

当△ > 0 时，方程有两个不同的实数根

当△ < 0 时，方程无实数解

当△ = 0 时，方程有两个相同的实数根

结语

众所周知，OI是一种融汇了各个学科知识的东西，所以大家在学习OI的时候也不能荒废了学业，whk成绩一定要搞好，不少大佬都最后因为失误落得一个很惨的下场