有是一个大数相乘的题目的运用,用C++嘛,这里纯手工打造大数相乘。创建一个class,然后使用hash表,查表就是常数的效率了。
You are asked to calculate factorials of some small positive integers.
Input
An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.
Output
For each integer n given at input, display a line with the value of n!
Example
Sample input:
4
1
2
5
3
Sample output:
1
2
120
6
手工打造,我觉得尽管题目有限制数据,自己还是习惯地检验一下好,养成优良习惯。
100的阶乘是个非常非常大的数,所以这里使用string实现大数相乘了。
#include <iostream>
#include <vector>
#include <string>
#include <assert.h>
#include <algorithm>
using namespace std;
class BigNum
{
string table[101];
string numToStr(int n)
{
if (0 == n) return "0";
string s;
while (n)
{
s.push_back(n % 10 + '0');
n /= 10;
}
reverse(s.begin(), s.end());
return s;
}
public:
BigNum()
{
table[0] = "0", table[1] = "1";
for (int i = 2; i < 101; i++)
{
table[i] = bigMultiply(numToStr(i), table[i-1]);
}
cout<<endl;
}
string bigMultiply(string a, string b)
{
if (a.empty() || b.empty() || '0' == a[0] || '0' == b[0]) return "0";
string c(a.size() + b.size(), '0');
for (int i = a.size() - 1; i >= 0 ; i--)
{
int carry = 0;
int an = a[i]-'0';
for (int j = b.size() - 1; j >= 0 ; j--)
{
int bn = b[j] - '0';
int sum = an * bn + carry + c[i+j+1] - '0';
carry = sum / 10;
c[i+j+1] = sum % 10 + '0';
}
if (carry) c[i] += carry;
}
if (c.size() && '0' == c[0]) c.erase(c.begin());
return c;
}
void SmallFactorialRun()
{
int T = 0, N = 0;
cin>>T;
while (T--)
{
cin>>N;
assert(0<N && N<101);
cout<<table[N]<<endl;
}
}
};
int main()
{
BigNum bgn;
bgn.SmallFactorialRun();
return 0;
}
分享到:
相关推荐
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
My solution for some spoj problems
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
SPOJ-Solutions:SPOJ算法问题的解决方案
RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!
) :red_heart:附Oj平台平台地址BZOJ POJ 硬盘单元洛谷 代码VS 牛编码器 LibreOJ 编码部队 51点头 编码器 上海交大 最佳编码器 卢特斯 华东师范大学 SPOJ 宁波奥杰 Darkbzoj 虚拟法官 上下文猎人 维霍斯 公开评委小...
SPOJ-备份工具 介绍 在 Sphere Online Judge ( ) 中,您可以尝试所给的具有挑战性的问题。 它还使您能够查看和下载您自己的解决方案。 工具 SPOJ_BACKUP 备份所有已接受的提交并将它们保存在脚本所在的计算机位置。...
SPOJ-解决方案复合解决方案
SPOJ-解决方案SPOJ问题的解决方案,主要是java一些python。
Spoj-解决方案 我的连接解决方案
Spoj 用户工具基于 Django 的 Spoj 用户分析工具。 目前托管在 Google Appengine 上: ://spojtool.appspot.com/安装获取列出的包,并将它们放在指定的项目目录中。 为了安全,请修改 secret_key.py 中的 SECRET_KEY...
Spoj-解决方案 此存储库包含 spoj 问题的解决方案。 问题是通过他们的 id 来识别的。
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
SPOJ解决方案 最好的:我的SPOJ
Judge-允许使用各种各样的编程语言【SPOJ】 http://www.spoj.pl/ SGU Online Contester-具有模拟参加历史比赛的虚拟赛功能 http://acm.sgu.ru/ Codeforces-不断维护历届题库 http://codeforces.com 首先,...
SPOJ 应对spoj.com的挑战
竞技编程这个 repo 包含(几乎)所有程序: codechef.com codeforces.com 间谍网黑客等级网Hande : sananth12 在所有平台上统计数据代码总行数:22,410+ 程序总数:500+
我在C ++中针对Spoj托管的一些问题的解决方案 :laptop: 编码BUGLIFE 埃及披萨丽莎NFURY PT07Y TRT 地址BVAAN EKO LPIS 纽约10E PT07Z TWENDS 阿格罗夫CAM5 电动车MAIN12A ORDSUM23 里瓦尔斯ULM09 爱宝CODERE3 前脸...
复合溶液简单的CONNECT问题的解决方案。 参见: :
SPOJ调整在SPOJ网站上进行细微调整的Chrome扩展程序,在很大程度上基于的先前工作进行了调整,以适应网站的新布局。特征经典问题在问题集中的“用户”列旁边有一个“分数”列。 点数显示在经典问题的标签下,挑战...