题目链接:http://59.69.128.200/JudgeOnline/problem.php?pid=416
题目大意:
给你十个数A1,A2,A10.范围都是0到10000以内。N是这十个数相乘后的结果。求N的因子个数的个位数字。
解题思路:
这是很久以前抗电网赛的一道题目,其实也就是一个数论题。
用到的知识就是算数基本定理推论:
任一个大于1的整数a都能够唯一的写成
a=p1^a1*p2^a2……pk^ak > 0.
其中p1<p2<……<pk且pk为素数。
然后a的因子个数就是(a1 + 1)*(a2 + 1)*(a3 + 1)……*(ak + 1)。
解决这个问题需要注意地的方有:
素数打表问题,因为每个数都是10000以内的数,所以需要知道100以内的素数都是什么(至于为什么10000这个数只需要求出开方后的数字以内的素数,好像某个数学家证明过吧。。。。)
1.我用的打表方法是先把is_prim[i]全部初始化为1.然后从2开始,如果这个数标记为1,则把它的所有倍数全部标记为0(成倍肯定不是素数)。
这样外层循环100次,就可以求出100以内的素数,然后新开一个数组,将100以内的素数顺序记录下来,就可以处理10000以内的素数问题了。但是值得我们特别注意的是:这里如果素数处理后结果不为1,说明它含有大于100的素数,我们不需要处理,它肯定是素数。
2.我用map<int,int>ans来记录素数出现的次数。之后循环一遍就可以求出结果。
代码如下:
分享到:
相关推荐
信奥中的数学 数论 第5讲 唯一分解定理(算术基本定理).pdf
代数和数论中的程序计算问题之高斯整数环Z[i]、整数环Z等UFD的算术基本定理的C++程序实现
基于CCS2000的仿真实验报告以及实验代码,详细介绍了利用CCS软件实现算术运算的方法
对于基本的算术表达式,以字符序列的形式从终端进行输入,要求语法正确的,不含变量,按照算术运算优先级顺序,实现基本算术表达式的运算过程。 (1) 输入:输入一个算术表达式,以#结束 (2) 输出:输出数据栈...
教育资料
1002 算术基本运算 #.c
算术基本定理 约数 最大公约数和最小公倍数 互质与欧拉函数 2. 同余 模运算 基本概念 同余的性质 同余类和剩余系 费马小定理 欧拉定理 裴蜀定理 扩展 逆元 逆元求解 线性求逆元:递推/倒推 线性同...
算术编码 方法算术编码 算术编码 算术编码 算术编码
给定一个算术表达式,通过程序求出最后的结果。 1、从键盘输入要求解的算术表达式; 2、采用栈结构进行算术表达式的求解过程(不用栈结构验收不合格); 3、能够判断算术表达式正确与否; 4、对于错误表达式给出提示...
小学算术的加、减、乘、除及混合计算,在练习过程将计时,最终给出成绩。可限定计算数值范围。 安装:解压缩后SETUP安装即可。
这个是用堆栈的方式来实现算术表达式,有良好的用户界面
算术编码详解及习题,算术编码基本原理,对初学者有帮助
用python实现算术编码,能够实现编码与译码。编码的方法是通过对一篇已知文章求取概率空间后,对待翻译文章进行算术编码,并能够基于已知文章重新进行算术解码。
问题描述:一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。...基本要求: (1) 从键盘读入一个合法的算术表达式,输出正确的结果。 (2) 显示输入序列和栈的变化过程。
为使二项式定理系列能涵盖更多的内容,扩大其使用的范围,笔者独辟蹊径,从对称多项式基本定理出发,由考虑二元齐次对称多项式与二项式定理间的关系入手,取得了可喜的进展。 众所周知,二元齐次对称多项式的一般...
计算机组成原理运算器实验—算术逻辑运算实验 (2).pdf计算机组成原理运算器实验—算术逻辑运算实验 (2).pdf计算机组成原理运算器实验—算术逻辑运算实验 (2).pdf计算机组成原理运算器实验—算术逻辑运算实验 (2).pdf...
算术研究英文版_高斯 算术研究英文版_高斯
《计算机组成原理》实验报告---8位算术逻辑运算实验.docx《计算机组成原理》实验报告---8位算术逻辑运算实验.docx《计算机组成原理》实验报告---8位算术逻辑运算实验.docx《计算机组成原理》实验报告---8位算术逻辑...
这是数据结构课程设计,二叉树表示的算术表达式
算术编码C++实现,概率自适应方法进行算术编码和解码