前言：
比赛的时候想出了三种做法，暴力，二分还有数学。额，实测暴力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还必须满足什么条件（前置知识：整式的乘除）。
我们已知：
展开就是：
化简可得：
题目中说：
将 $ n_i $ 代入式中可得：
稍稍变化一下，可以得出：
怎么样？是不是发现题目中的变量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<<"NOn";
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
实测上面代码赛中70pts，Luogu50pts。
Step2 数学：
额，按照暴力做法继续向下推：
上次写到哪了？嗷对，写到(p_i + q_i)了，就是这个式子：
我们是不是还有(p_i times q_i)？
连立上面的两个式子（即 $p_i + q_i = n_i - e_i times d_i + 2 $ 与 (p_i times q_i = n)）可得：
再将我们已经得出的(p_i + q_i)和(p_i times q_i)代入式子中得出：
整理可得：
整理可得：
整理可得：
很好，现在我们有了(p_i + q_i) 与 (p_i - q_i)，不就能求(p_i)和(q_i)了么：
这样的(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<<"NOn";
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
Step3 二分：
二分解法是从暴力的思路继续向下推导的：
话说上面写到了这个式子：
也就是(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
#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<<"NOn";
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
完结撒花！
文章来源: 博客园
原文链接: https://www.cnblogs.com/xinao2186182144/p/17216386.html
- 还没有人评论，欢迎说说您的想法！
客服
