机器人繁殖
X星系的机器人可以自动复制自己。它们用1年的时间可以复制出2个自己，然后就失去复制能力。每年X星系都会选出1个新出生的机器人发往太空。也就是说，如果X星系原有机器人5个，1年后总数是：5 + 9 = 14，2年后总数是：5 + 9 + 17 = 31。如果已经探测经过n年后的机器人总数s，你能算出最初有多少机器人吗？
数据格式：
输入一行两个数字n和s，用空格分开，含义如上。n不大于100，s位数不超过50位。
要求输出一行，一个整数，表示最初有机器人多少个。
-
例如，用户输入：2 31，则程序应该输出：5
再例如，用户输入：97 2218388550399401452619230609499，则程序应该输出：8
资源约定：
峰值内存消耗 < 512M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…”的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSIC/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
通过手算，可以发现原来有x个机器人，n年后机器人数量为a*x+a-n-1,其中a为首项为一，公比为二等比数列的前n（n年）项和。
此题难点在于运算的数字可能非常大，超出了常用的几种数据类型的范围。所以思路是用数组来进行大数的加法运算。
#include <iostream> #include <cstring> #include <cstdio> using namespace std; //大数求和 void Sum(int a[],int b[],int c[]) { int i; for (i = 0; i < 50; i++) c[i] = 0; int temp = 0; for (i = 0; i < 50; i++) { temp = temp/10 + a[i] + b[i]; c[i] = temp % 10; } } //求送走多少人 void D(int x,int s[]) { int i,temp; int r[50] = {0}; r[0] = 1; int k = 0; while(k < x){ temp = 0; for (i = 0; i < 50; i++) { temp = temp/10 + 2*r[i]; r[i] = temp % 10; } temp = -10;//每年送走一个人 for (i = 0; i < 50; i++) { temp = temp/10 + s[i] + r[i]; s[i] = temp % 10; } k++; } if (s[0] < 0) { s[0] = 10 + s[0];s[1]--; } } //求人数翻了多少倍 void D1(int x,int s[]) { s[0] = 1; int i,temp; int r[50] = {0}; r[0] = 1; int k = 0; while(k < x){ temp = 0; for (i = 0; i < 50; i++) { temp = temp/10 + 2*r[i]; r[i] = temp % 10; } temp = 0; for (i = 0; i < 50; i++) { temp = temp/10 + s[i] + r[i]; s[i] = temp % 10; } k++; } } //寻找恰当的比例 int Cheng(int i,int a[],int b[]) { int temp = 0,j,flag = 1; for (j = 0; j < 50; j++) { temp = temp/10 + i * a[j]; if (b[j] != temp)flag = 0; } return flag; } int main() { int i,j; int a[50] = {0},b[50] = {0},c[50] = {0}; char d[50]; int n; cin >> n; scanf("%s",d); for (i = 0; i < strlen(d); i++) a[strlen(d)-i-1] = (int)d[i]-48; D(n,b); Sum(a,b,c); memset(a,0,sizeof(a)); D1(n,a); for (i = 1; i < 100; i++) { if (Cheng(i,a,c)){cout << i <<endl;break;} } return 0; }
