题目描述
X 星系的机器人可以自动复制自己。它们用 1 年的时间可以复制出 2 个自己，然后就失去复制能力。
每年 X 星系都会选出 1 个新出生的机器人发往太空。也就是说，如果 X 星系原有机器人 5 个，1 年后总数是：5 + 9 = 14，2 年后总数是：5 + 9 + 17 = 31。
如果已经探测经过 n年后的机器人总数 s，你能算出最初有多少机器人吗？
输入描述
输入一行两个数字 n 和 s，用空格分开，含义如上。n不大于 100，s位数不超过 50 位。
输出描述
要求输出一行，一个整数，表示最初有机器人多少个。
输入输出样例
示例 1
输入
2 31
输出
5
示例 2
输入
97 2218388550399401452619230609499
输出
8
想法：
- 先正推出公式，原有a个机器人，总数为是，s=a，第一年就是a+a*2-1，第二年就是s-a的差 * 2 -1
- 所以s为数组，今年的数等于去年的数-前年的数的差×2-1
自己的想法是通过找规律逆推出结果，发现行不通，参考别人代码后，明白了主要还是通过正推推出匹配的条件后得出结果，虽然时间复杂度高，但是还没有别的办法。
#include<bits/stdc++.h>
using namespace std;
int n;
long long s;
long long res(long long a,long long b){
for(long long i = 1;i<=n;++i){
a = a*2-1;
b+=a;
}
return b;
}
int main(){
cin >> n >> s;
for(long long i = 1;i <=s;++i){
if(res(i,i) == s){
cout << i << endl;
return 0;
}
}
}
有一个超时了
把所有long long改成double
#include<bits/stdc++.h>
using namespace std;
double n;
double s;
double res(double a,double b){
for(double i = 1;i<=n;++i){
a = a*2-1;
b+=a;
}
return b;
}
int main(){
cin >> n >> s;
for(double i = 1;i <=s;++i){
if(res(i,i) == s){
cout << i << endl;
return 0;
}
}
return 0;
}
- 其中关于类型进行了整理，因为不小于50位，所以使用double而不是long long。
