ACM程序设计-计算简单题.ppt

简单计算题 ACM程序设计 2 31 列出完数 题目内容自然数中 完数寥若晨星 请在从1到某个整数范围中打印出所有的完数来 所谓 完数 是指一个数恰好等于它的所有不同因子之和 例如 6是完数 因为6 1 2 3 而24不是完数 因为241 2 3 4 6 8 12 36 输入描述输入数据中含有一些整数n 1 n 10000 3 31 输出描述对于每个整数n 输出所有不大于n的完数 每个整数n的输出由n引导 跟上冒号 然后是由空格开道的一个个完数 每个n的完数列表应占独立的一行 输入样例1005000输出样例100 6285000 628496 4 31 题目分析 如果针对每个整数都搜索一次完数 时间会花费较多 由于完数较少 可以先找出10000以内的所有完数 然后再针对n查表 5 31 参考源代码 includeintmain void inti j k 0 n sum a 100 for i 2 i 10000 i 2 已知完数为偶数 sum 1 for j 2 j i 2 j if i j 0 sum j if sum i a k i 6 31 参考源代码 while scanf d 7 31 对称三位数素数 题目内容判断一个数是否为对称三位数素数 所谓 对称 是指一个数 倒过来还是该数 例如 375不是对称数 因为倒过来变成了573 输入描述输入数据含有不多于50个的正整数 0 n 2 32 输出描述对于每个n 如果该数是对称三位数素数 则输出 Yes 否则输出 No 每个判断结果单独一行 8 31 输入样例11101272输出样例NoYesNo 9 31 题目分析 三位对称只须判断个数与百位是否相等 10 31 参考源代码 include includeintisprime inta inti ints int sqrt double a for i 2 i s i if a i 0 return0 return1 11 31 参考源代码 intmain void intn while scanf d 12 31 五位以内的对称素数 题目内容判断一个数是否为对称且不大于五位数的素数 输入描述输入数据含有不多于50个的正整数n 0 n 2 32 输出描述对于每个n 如果该数是不大于五位数的对称素数 则输出 Yes 否则输出 No 每个判断结果单独列一行 13 31 输入样例11101272输出样例YesYesNo 14 31 题目分析 怎样判断每位对称素数 15 31 参考源代码 includeintisprime intn inti if n 1 1不是素数return0 if n 2 16 31 参考源代码 intissym intn if n100 17 31 参考源代码 intmain void intn while scanf d 18 31 Aneasyproblem TimeLimit 6000 3000MS Java Others MemoryLimit 32768 32768K Java Others 19 31 ProblemDescriptionWhenTeddywasachild hewasalwaysthinkingaboutsomesimplemathproblems suchas Whatit s1cupofwaterplus1pileofdough 100yuanbuy100pig etc OnedayTeddymetaoldmaninhisdream inthatdreamthemanwhosenamewas RuLai gaveTeddyaproblem GivenanN canyoucalculatehowmanywaystowriteNasi j i j 0 i j TeddyfoundtheanswerwhenNwaslessthan10 butifNgetbigger hefounditwastoodifficultforhimtosolve Well youcleverACMers couldyouhelplittleTeddytosolvethisproblemandlethimhaveagooddream 20 31 InputThefirstlinecontainaT T 2000 followedbyTlines eachlinecontainanintegerN 0 N OutputForeachcase outputthenumberofwaysinoneline 21 31 Sampleinput 213Sampleoutput 01 22 31 题目分析 思路1 将等式变形为N 1 i 1 j 1 由于i j 只需要枚举i 枚举范围从1到 然后判断是否满足 直接计数即可 23 31 思路2 同样将等式变形N 1 i 1 j 1 只需要求出N 1的约数个数 然后分情况处理即可 令N 1的约数个数为f N 1 1 当N 1为完全平方数时 ans f N 1 2 1 2公式可以理解成 所有的约数 去掉1和本身之后 减2 剩下的可以对称的组成一对一对的答案 24 31 而分解质因数最有效的方法就是筛出范围内的素数表 然后依次试除 2 当N 非完全平方数 同理可得 ans f N 1 2 2 如何快速的求一个数N的约数个数我们知道 任何一个自然数N可以表示成其质因数的幂的乘积的形式 由排列组合的乘法原理知 N的约数个数f N a1 1 a2 1 an 1 25 31 1 简单的筛素数 其思想是 先假定所有的数都是素数 然后从2开始依次筛掉素数的倍数的数 26 31 constintMax 100000 boolbp Max 1 记录每个数是否是素数intp 30000 记录筛选出来的素数intpCnt 0 记录当前筛选出来的素数个数voidsieveP