#大数加减乘除#校赛D题solve

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std; const static int M = 50; int numA[M];
int numB[M]; //使用string重置numA
void resetNumA(string numAStr)
{
memset(numA,0,M*sizeof(int)); //将字符串的每一位都转换成数字传入数组
for (int i = 0; i < numAStr.length(); i++)
{
numA[i] = numAStr[numAStr.length()-i-1] - '0';
}
} //使用string重置numB
void resetNumB(string numBStr)
{
memset(numB,0,M*sizeof(int)); //将字符串的每一位都转换成数字传入数组
for (int i = 0; i < numBStr.length(); i++)
{
numB[i] = numBStr[numBStr.length()-i-1] - '0';
}
} //将数组转换为字符串,用于输出
string getNumString(int* num)
{
string numString;
bool isBegin = false;
for (int i = M-1; i >= 0 ; i--)
{
if(num[i] != 0)
{
isBegin = true;
} if (isBegin)
{
numString += num[i] +'0';
}
}
return numString;
} //判断两个数字哪个大
int compare(string numAStr,string numBStr)
{
if (numAStr.length() > numBStr.length())
{
return 1;
}
else if (numAStr.length() < numBStr.length())
{
return -1;
}
else
{
for (int i = 0; i < numAStr.length(); i++)
{
if (numAStr[i]>numBStr[i])
{
return 1;
} if (numAStr[i]<numBStr[i])
{
return -1;
}
}
return 0;
}
} //加法
string add(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr); for (int i = 0; i < M; i++)
{
//结果保存在numA中
numA[i] += numB[i]; //数字大于9则进位
if(numA[i]>9)
{
numA[i] -= 10;
numA[i+1]++;
}
} return getNumString(numA);
} //减法
string ab(string numAStr, string numBStr)
{
bool isNegative = false; //如果numA比numB小
//则结果为负数
//调换位置进行计算
if (compare(numAStr,numBStr)==-1)
{
isNegative = true;
string temp = numAStr;
numAStr = numBStr;
numBStr = temp;
}
else if (compare(numAStr,numBStr)==0)
{
return "0";
} resetNumA(numAStr);
resetNumB(numBStr); for (int i = 0; i < M; i++)
{
//减数小于被减数就借位
if (numA[i]<numB[i])
{
numA[i] = numA[i]+10-numB[i];
numA[i+1]--;
}
else
{
numA[i] -= numB[i];
}
}
if (isNegative)
{
return "-"+ getNumString(numA);
}
else
{
return getNumString(numA);
} } //乘法 string mul(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr); vector<string> nums;
for (int i = 0; i < numBStr.length(); i++)
{
//初始化一个临时数据来保存被乘数与乘数的某一位相乘的结果
int temp[M];
memset(temp,0,M*sizeof(int)); for (int j = i; j < numAStr.length()+i; j++)
{
temp[j] += numA[j-i]*numB[i]%10; temp[j+1] = numA[j-i]*numB[i]/10; //如果大于9,那么就做进位处理
if (temp[j]>9)
{
temp[j]-=10;
temp[j+1]++;
}
}
nums.push_back(getNumString(temp));
} //每位相乘的结果再用加法加起来
string result = nums[0];
for (int i = 1; i < nums.size(); i++)
{
result = add(result,nums[i]);
} return result;
} //除,结果精确到个位
string div(string numAStr, string numBStr)
{
resetNumA(numAStr);
resetNumB(numBStr); string result;
string left; if (compare(numAStr,numBStr)==-1)
{
return "0";
} //标记第一个不为0的位数的出现
bool flag = false;
for (int i = 0; i < numAStr.length(); i++)
{
left +=numAStr[i]; //余数比除数大
if (compare(left,numBStr)==1)
{
flag = true; int cnt = 1;
string temp = numBStr; while (true)
{
//每循环一次加上一个余数
temp = add(temp,numBStr); //余数仍然大于除数,继续累加
if (compare(left,temp)==1)
{
cnt++;
}
//余数小于除数
//可以计算结果
else if (compare(left,temp)==-1)
{
result += cnt + '0';
left = ab(left, ab(temp,numBStr));
break;
}
//此时余数刚好是除数的倍数
else if (compare(left,temp) == 0)
{
cnt ++;
result += cnt + '0';
left = "";
break;
}
}
}
//刚好除尽
else if(compare(left,numBStr)==0)
{
flag = true;
result +="1";
left = "";
}
//余数比除数小,跳到下一位
else if(flag&&compare(left,numBStr)==-1)
{
result +="0";
left="";
} } return result;
} int getMod(string s)
{
int len=s.length();
int ans=0;
for(int i=0;i<len;i++)
ans=(ans*10+s[i])%2;
return ans;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string str;
cin>>str;
string s1="1",s2="2";
string str2=div(str,s2);
string ans=mul(str2,ab(str2,s1));
if(getMod(str)==1)
ans=add(ans,ab(div(add(str,s1),s2),s1));
cout<<ans<<endl;
}
}
上一篇:PHP中的抽象类与抽象方法/静态属性和静态方法/PHP中的单利模式(单态模式)/串行化与反串行化(序列化与反序列化)/约束类型/魔术方法小结


下一篇:POJ 1716 Integer Intervals#贪心