前言：
比賽的時候想出了三種做法，暴力，二分還有數學，額，實測暴力70pts，二分100pts，數學100pts，但是比賽的時候這道題還是保齡了（我才不會告訴你我，在這寫下題解算是警戒和紀念吧（freopen除錯的時候加的注釋沒有刪掉呢紀念保齡，這里介紹暴力，二分，數學三種做法，不過二分的代碼我給刪了，先放一下其他大佬的代碼吧（當然是照著敲一遍的，我才懶得找人家說明情況
題目：
Luogu:Link
簡要：
給定一個正整數 \(k\)，有 \(k\) 次詢問，每次給定三個正整數 \(n_i, e_i, d_i\)，求兩個正整數 \(p_i, q_i\)，使 \(n_i = p_i \times q_i\)、\(e_i \times d_i = (p_i - 1)(q_i - 1) + 1\)，
輸入格式
第一行一個正整數 \(k\)，表示有 \(k\) 次詢問，
接下來 \(k\) 行，第 \(i\) 行三個正整數 \(n_i, d_i, e_i\)，
輸出格式
輸出 \(k\) 行，每行兩個正整數 \(p_i, q_i\) 表示答案，
為使輸出統一，你應當保證 \(p_i \leq q_i\)，
如果無解，請輸出 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
Step 1 暴力：
額，暴力做法非常簡單，照著題意直接敲就好了，用兩層For回圈分別列舉p和q的話肯定會T得很慘，那么考慮優化，
我們不妨來看看p和q還必須滿足什么條件（前置知識：整式的乘除），
我們已知：
\[e_i \times d_i = (p_i - 1)(q_i - 1) + 1 ; \]展開就是：
\[e_i \times d_i = p_i \times q_i - p_i - q_i + 1 + 1 ; \]化簡可得：
\[e_i \times d_i = p_i \times q_i - (p_i + q_i) + 2 ; \]題目中說：
\[n_i = p_i \times q_i ; \]將 $ n_i $ 代入式中可得：
\[e_i \times d_i = n_i - (p_i + q_i) + 2 ; \]稍稍變化一下，可以得出：
\[p_i + q_i = n_i - e_i \times d_i + 2 ; \]怎么樣？是不是發現題目中的變數m的范圍有用了？這也就證明我們的做法是正確的，其實到這里我們已經很接近正解了，不過呢如果為了節省時間，現在已經可以敲代碼了！
代碼：
Link
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t;
int n;
int m;
int k;
int l;
int r;
int s;
inline int read(){
int s=0;
int w=1;
char ch;
ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
w=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void write(int s){
if(s<0){
putchar('-');
s=~s+1;
}
if(s>9){
write(s/10);
}
putchar(s%10+'0');
return ;
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
t=read();
while(t--){
n=read();
m=read();
k=read();
l=n-m*k+2;
bool a=false;
for(int i=1;i<=n-m*k+2;i++){
int j=n-m*k+2-i;
if(i*j==n&&((i-1)*(j-1)+1==m*k)){
write(min(i,j));
putchar(' ');
write(max(i,j));
putchar('\n');
a=true;
break;
}
}
if(a==false){
cout<<"NO\n";
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
實測上面代碼賽中70pts，Luogu50pts，
Step2 數學：
額，按照暴力做法繼續向下推：
上次寫到哪了？嗷對，寫到\(p_i + q_i\)了，就是這個式子：
\[p_i + q_i = n_i - e_i \times d_i + 2 ; \]我們是不是還有\(p_i \times q_i\)？
\[p_i \times q_i = n; \]連立上面的兩個式子（即 $p_i + q_i = n_i - e_i \times d_i + 2 $ 與 \(p_i \times q_i = n\)）可得：
\[p_i - q_i = \pm \sqrt{ (p_i + q_i) ^ 2 - 4 \times p_i \times q_i }; \]再將我們已經得出的\(p_i + q_i\)和\(p_i \times q_i\)代入式子中得出：
\[p_i - q_i = \pm \sqrt{ (n_i - e_i \times d_i + 2) ^ 2 - 4 \times n_i } \]整理可得：
\[p_i - q_i = \pm \sqrt{ (n_i - e_i \times d_i) ^ 2 + 4 \times n_i - 4 \times e_i \times d_i + 4 - 4 \times n_i}; \]整理可得：
\[p_i - q_i = \pm \sqrt{ n_i ^ 2 + e_i ^ 2 \times d_i ^ 2 - 2 \times n_i \times e_i \times d_i + 4 \times n_i - 4 \times e_i \times d_i + 4 - 4 \times n_ig}; \]整理可得：
\[p_i - q_i = \pm \sqrt{ n_i ^ 2 + e_i ^ 2 \times d_i ^ 2 - 2 \times n_i \times e_i \times d_i - 4 \times e_i \times d_i + 4}; \]很好，現在我們有了\(p_i + q_i\) 與 \(p_i - q_i\)，不就能求\(p_i\)和\(q_i\)了么：
\[p_i = \frac{n_i - e_i \times d_i + 2 - \sqrt{ n_i ^ 2 + e_i ^ 2 \times d_i ^ 2 - 2 \times n_i \times e_i \times d_i - 4 \times e_i \times d_i + 4}}{2}; \]\[q_i = \frac{n_i - e_i \times d_i + 2 + \sqrt{ n_i ^ 2 + e_i ^ 2 \times d_i ^ 2 - 2 \times n_i \times e_i \times d_i - 4 \times e_i \times d_i + 4}}{2}; \]這樣的\(p_i\)和\(q_i\)就能滿足\(p_i\)比\(q_i\)小了，
額，得出來的\(p_i\)和\(q_i\)若不滿足題目要求就是無解的情況啦！
代碼：
Link
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t;
int n;
int m;
int k;
int l;
int r;
int s;
int p;
int q;
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>t;
while(t--){
cin>>n>>m>>k;
l=n-m*k+2;
p=(l-sqrt(l*l-4*n))/2;
q=(l+sqrt(l*l-4*n))/2;
if(p*q==n||((p-1)*(q-1)+1)==m*k){
cout<<p<<" "<<q<<"\n";
}
else{
cout<<"NO\n";
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
Step3 二分：
二分解法是從暴力的思路繼續向下推導的：
話說上面寫到了這個式子：
\[p_i + q_i = n_i - e_i \times d_i + 2 ; \]也就是\(p_i + q_i\)是一定的，那么根據和積原理，\(p_i + q_i\)具有單調性，所以我們就可以使用二分查找列舉\(p_i\)或\(q_i\)來尋找答案啦！
在這里，我們列舉\(p_i\)來找到答案，原因有兩點：
-
\(p_i\)是較小值，只需列舉至\(\frac{p_i + q_i}{2}\)就可以得出答案了；
-
比起q我更喜歡p這個字母；
有不會和積原理的童鞋看這：
參考網：Link
Luogu：Link
（反正我是都沒看懂，比賽的時候直接用的二分，根本沒考慮單調性，但是還是過了
代碼：
Link
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k;
int n;
int e;
int d;
int h;
int x;
int sx;
int ef(int l, int r, int n, int m){
while(l<=r){
int mid=((l+r)>>1);
int j=mid*(m-mid);
if(j==n){
return mid;
}
else{
if(j<n){
l=mid+1;
}
else{
r=mid-1;
}
}
}
return -114514;
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>k;
while(k--){
cin>>n>>e>>d;
h=n-e*d+2;
sx=ceil(h/2);
x=ef(1ll,sx,n,h);
if(x!=-114514){
cout<<x<<" "<<h-x<<"\n";
}
else{
cout<<"NO\n";
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
完結撒花！
本文來自博客園，作者：Taunting_Wind，轉載請注明原文鏈接：https://www.cnblogs.com/xinao2186182144/p/17216386.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/547227.html
標籤：C++
上一篇：zynq基于DMA的串口傳圖