技术丨ACM大神详解最新北美面试题第四讲总结
?题目1 BigInt Manipulation
即求两个非常大的整数乘积问题。
这道题目要解决的问题是，数字过大导致无论是数字本身还是最后的乘积都无法用单纯的变量存储，所以我们可以用数组来表示非常大的数字。而这种数组表示，其实就是模拟了人类计算乘法的方法，也就是按照每一位来计算乘积后，把这些单个的乘积相加起来就是最后的结果。如下图：
所以这里需要一个双重循环，对a和b的每一个位上的数字进行乘法计算，将乘积存到数组c。这里需要注意的是如果c某一位的数字大于10则需要对这位进行carry进位，而我们人类进位时，都是从小位往大位近，如下图：
注：最后一行代码更正 * c[ k ] = c[ k ] % 10
同时需要注意，虽然n位的a乘以m位的b最多有n+m-1位，但是最后进最后一位的时候可能需要进到更高位，即n+m位，所以这里c的长度为n+m，如下图：
此外，需要考虑0的特殊情况，需要将最后结果c中所有前导均为0的位去掉，如下图：
复杂度的话，因为有一个双重循环，所以肯定是O(n * m ) 级别，再加上要carry进位和检查前导0的情况，最后的复杂度如下图：
其实对于大整数相乘，我们可以采用压缩数位的方法来节省存储空间，即对于array中的每一位，如果每位存储两位数字，更能省空间。但需要注意如果存储四位数字，可能出现乘积溢出变成负数的情况，如下图：
?题目2 Miller Rabin Primality Test
给定一个数N，判断是否为质数，如下图：
暴力解法的话，从2到N-1，看能不能整除N。虽然O(N) 但是如果N很大则太费时。进一步优化的话，如果K * R = N, 那么K或者R中有一个是小于等于N的平方根，如下图。所以我们可以用上边同样的方法不过是从2到N平方根逐一检查，但依旧会很耗时间。
下面引入费马定理：如果x和p互质，即不能互相整除，gcd(x, p) = 1，那么 x^(p-1) mod p = 1，或 x^p mod p = p。根据费马定理，如果N为质数，对于1 &= x & N，x都会满足费马定理，反之N可被x整除不是质数。所以必须找到至少一个反例，即存在小于N的x使 x^(N-1) mod N ≠ 1，才能说明N不为质数。而如果找了很多x都没找到这样的反例，虽然不能说明N不是质数，但是N是质数的可能性是越来越大的，但是x的挑选也需要注意，所以这个方法还是有些难以实现。如下图，如果x=2，N=341，的确可以满足费马定理，但实际上341不是质数。
另一种方法叫做Miller-Rabin质数测试，类似于费马定理，也是要选取某个值来测试N是否为质数。首先，引入另外一个定理：如果一个数y满足 y^2 mod p = 1，0 &= y & p，那么y要么等于1，要么等于p -1。
再结合费马定理：如果存在x满足 x^(p-1) mod p = 1，而且p为奇数（否则偶数肯定不是质数），即x^(p-1)存在开方根，且p为质数（p相当于是要被判断是否为质数的N），那么x^(p-1)的平方根就等于1或者p-1，即费马定理中的 x^(p-1) 相当于上边定理中的y^2；否则，p不为质数。比如下边图中的例子，x为2，N为341，进行到最后2 85 mod 341 = 32 ≠1，则341不是质数。
复杂度的话，假设选取P个x，总共O(logN)轮验证（每次都要不断地求平方根即除以2），每次验证都需要O(logN)次，总共的复杂度就是O(P(logN)^2)。具体算法实现如下：
?题目3 Euler Primality Test
给定一个数N，找到比N小的所有素数。
暴力解法，枚举所有的比N小的数字，逐个检验是否是素数，但是这个方法太过费时间。更好的方法叫做Eratosthenes素数检验。如果一个数字是质数，则它的倍数不会是质数，比如2为质数，但是4、6、8就不是。根据这个思路，枚举所有数字，每个数字单独验证，就是筛选掉那些质数的倍数。算法复杂度O(NlogN)，即每一个数字要被验证logN次，但实际时间复杂度可以达到O(Nlog(logN))，如下图。
但是这个方法会有重复筛选的情况，如下图。如何对一个数只筛选一次（比如30可以被2、3、5筛选）？以及质数的特别之处在哪里（最小质因数）？在原视频中讲解了欧拉素数检测法，具体算法实现如下图，复杂度的话，只需要遍历所有的N即可，这是一个最优解。欢迎各位去太阁官网观看原视频。
责任编辑：
声明：本文由入驻搜狐号的作者撰写，除搜狐官方账号外，观点仅代表作者本人，不代表搜狐立场。
今日搜狐热点您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
ACM入门介绍.ppt 29页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
你可能关注的文档：
··········
··········
一些初学者必须要知道的问题 1.如何用C/C++处理输入输出2.复杂度和程序优化3.初学者如何进行修炼 1.如何用C/C++进行输入输出
相对次要的问题，但成为很多初学者的拦路虎 C/C++（尤其是C）输入输出方法较复杂，需要一定时间实践才能精通 我的任务：通过实例提供处理各种输入输出任务的方法，并讲解一些原则性的问题，同学们可以举一反三 首先，几个基本概念 什么是标准输入、标准输出？ 标准输入(stdin)：键盘(scanf, cin) 标准输出(stdout)：屏幕(printf, cout) 建议程序中只使用stdin和stdout 要打开文件怎么办？ freopen(“input.txt”, “r”, stdin); freopen(“output.txt”, “w”, stdout); ACM/ICPC中基本上都是要求从键盘输入，屏幕输出 是人工评测？ 否，测试前程序被做了重定向，就向上面一样，只不过重定向是外部的 比如，Linux Shell下 $ ./prog & input & output $ diff output answer 所以，严格按照题目描述来进行输入输出，不要打印任何题目未做要求的信息
ACM/ICPC的输入输出特点：流式、ASCII 顺序输入、输出，避免使用文件定位函数（如：fseek) 不需要把所有的输出放在一处进行，随时都可以输出，只要顺序是对的，因为只有当你的程序终止了，与正确答案的比较才会开始 字符格式，12345是5个字符‘1’,’2’,’3’,’4’,’5’构成 所以，C中只能使用处理ACSII文件的输入输出函数(getchar,putchar,scanf,printf,gets,fgets,puts) 使用C++进行输入输出 cin,cout 优点 数据类型自识别，使用简单 缺点 速度慢！ ACM/ICPC的测试数据规模非常大，cin/cout在这种情况下会成为性能瓶颈，引发超时 除非输入规模小，否则不推荐使用cin! 输出规模相对较小，在某些情况下使用cout会很方便，但是cout控制输出格式不如printf灵活 一个重要的误区 不要在一个程序中同时使用cin和C输入函数（如：scanf) 也不要同时使用cout和C输出函数（如：printf) 但是，可以C输入函数和cout搭配使用，反之亦然 违反以上原则可能导致输入/输出结果错误（会发生乱序）！
推荐使用C函数进行输入输出 输出：printf(putchar,puts)，其用法请查阅相关书籍，比较简单，不做重点讲解 每一行输出完后要打印回车’\n’，包括最后一行 输入：scanf, fgets(gets), getchar scanf 输入格式 %d %lld
%c %s %lf 对每种格式搞清楚一个重要问题 是否自动跳过前导空白？ 什么是空白：空格，TAB，回车
%d %lld %lf自动扫描前导空格 比如：读入5个整数到A[5] 输入文件中，数的排布是这个样子 35 26
206 不管它，直接5次%d for ( int i = 0; i & 5; i++ ) scanf(“%d”, A + i); %lld用于输入和输出长整数(long long,64位) %lf用于输入输出double
%s 读一个字符串，自动扫描前导空白，读到空白结束 如：
abcd efgh，将读出”abcd” %c读一个字符，但是不扫描前导空白 如何读一个非空白字符呢？ 比如，读取某人的信息，其性别用M/F表示 Nathan
Flying Claire
Self-healing 名字和能力用%s读，性别怎么办，自己扫描空格？麻烦！ 读一个非空白字符，方法一 char str[2]; scanf(“%1s”, str); // %s扫描前导空白，并且只读一个字符 char c = str[0]; 方法二 强制扫描空白 在%前面加上一个空格表示“强制扫描前导空白” scanf(“ %c”, &ch); 前面那个读人物信息的完整scanf语句： scanf(“%s %c %s”, name, &gender, ability);
同理，格式后面加一空格表示“读完这个变量后扫描空白”，注意空白是包括回车的 读一行：gets, fgets gets会导致很讨厌的warning message，所以可改用fgets fgets(str, sizeof str, stdin) = gets(str) 注意应使“下一个字符”处于这一行开头 有n个整数在一行上，但是n不知，只知道整数是空格分开的，怎么读？
正在加载中，请稍后...acm题中时间要求为1000ms的时间复杂度为多少？_百度知道
acm题中时间要求为1000ms的时间复杂度为多少？
请问，acm题中时间要求为1000ms的时间复杂度为多少？我做的时间复杂度为O（n2）的貌似过不了
我有更好的答案
报的啥错啊，超时的吗？这类试题一般测试数据不怎么大，时间上是完全足够出结果的。要不贴出链接看看
采纳率：83%
为您推荐：
其他类似问题
时间复杂度的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。}