宁波网站建设排名,寿光网站建设,网页设计与制作常识,网站ui怎么做的【题目来源】https://www.luogu.com.cn/problem/P8814https://www.acwing.com/problem/content/4732/【题目描述】 给定一个正整数 k#xff0c;有 k 次询问#xff0c;每次给定三个正整数 ni#xff0c;ei#xff0c;di#xff0c;求两个正整数 pi#xff0c;qi#xf…【题目来源】https://www.luogu.com.cn/problem/P8814https://www.acwing.com/problem/content/4732/【题目描述】 给定一个正整数 k有 k 次询问每次给定三个正整数 nieidi求两个正整数 piqi使 nipi×qiei×di(pi−1)(qi−1)1。【输入格式】 第一行一个正整数 k表示有 k 次询问。 接下来 k 行第 i 行三个正整数 nidiei。【输出格式】 输出 k 行每行两个正整数 piqi 表示答案。 为使输出统一你应当保证 pi≤qi。 如果无解请输出 NO。【输入样例】 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【输出样例】 2 385 NO NO NO 11 78 3 241 2 286 NO NO 6 88【数据范围】 以下记 mn−e×d2。 保证对于 100% 的数据1≤k≤10^5对于任意的 1≤i≤k1≤ni≤10^181≤ei×di≤10^181≤m≤10^9。【算法分析】 1已知 ed(p−1)(q−1)1pq−p−q11又已知 npq可得 edn−p−q2即 pqn-ed2。若记 mn-ed2则 2又由 (pq)^2p^22pqq^2 (p-q)^2p^2-2pqq^2可得 (pq)^2-(p-q)^2(p^22pqq^2)-(p^2-2pqq^2)4pq即 (p−q)^2(pq^)2−4pq开根号得即 3联立可得。同时根据题目要求p、q 必须是正整数若令 则当 ((mt)%21 || (m-t)%21 || mt) 时无解。【算法代码】
#includebits/stdc.h
using namespace std;typedef long long LL;
LL k,n,d,e;int main() {cink;while(k--) {cinnde;LL mn-d*e2;LL km*m-4*n;LL tsqrt(k);if(t*t!k) {coutNOendl;continue;}if((mt)%21 || (m-t)%21 || mt) {coutNOendl;continue;}cout(m-t)/2 (mt)/2endl;}return 0;
}/*
in:
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 109out:
2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
*/
【参考文献】https://www.luogu.com.cn/problem/solution/P8814
