牛客-[编程题]翻倍

链接：https://www.nowcoder.com/questionTerminal/e3a4a6f88e8b4b6ba20c4e25215b897b?answerType=1&f=discussion
来源：牛客网

小易给定你数字\mathit A,B(A < B)A,B(A<B)和系数\mathit p,qp,q。每次操作你可以将\mathit AA变成\mathit A+pA+p或者将\mathit pp变成\mathit p \times qp×q。问至少几次操作使得B \leq AB≤A。

输入描述:
第一行数据组数\mathit TT，对于每组数据，一行四个整数\mathit A,B,p,qA,B,p,q。
1 \leq A,p,B \leq 10^9 , 2 \leq q \leq 10 , 1 \leq T \leq 51≤A,p,B≤10
9
,2≤q≤10,1≤T≤5.

输出描述:
对于每组数据，输出一个数字表示答案
示例1
输入
2
1 5 7 2
3 5 1 2
输出
1
2
示例2
输入
2
1 15 4 2
12 19 3 2
输出
3
3
题解：搜索注意出口，一个不小心就会陷入死循环，话不多话，直接上代码
#include<bits/stdc++.h>
using namespace std;

int q,n;
void dfs(long A,long B,long p,int k){
if(A >= B){
if(n > k)n = k;
if(n == 0)n = k;
//printf("A=%d p=%d k=%d n=%d\n",A,p,k,n);
return;
}
else{
if(n!= 0 && n <= k)return;
dfs(A + p,B,p,k+1);
dfs(A,B,p*q,k+1);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
long A,B,p;
scanf("%d %d %d %d",&A,&B,&p,&q);
n=0;
dfs(A,B,p,0);
printf("%d\n",n);
}
}