(lecture_02)老少皆宜数学题 ACM课件

步骤：
a = 81, b = 63, a mod b = 18 a ← 63, b ← 18, a mod b = 9 a ← 18, b ← 9, a mod b = 0 所以9就是63与81最大条约数
第27页
欧几里德算法
欧几里德算法:
while b>0 do r←a%b a←b b←r
第一部分:同余相关
整除性质
欧几里德算法
扩展欧几里德算法
中国剩下定理
第二部分:素数相关
算术基本定理
欧拉定理
素数测试
Pollard rho方法
第7页
数论主要内容
第一部分:同余相关
整除性质
欧几里德算法
扩展欧几里德算法
中国剩下定理
第二部分:素数相关
算术基本定理
欧拉定理
素数测试
整除基本性质 欧几里德算法 扩展欧几里德算法 中国剩下定理
第43页
中国剩下定理
同模情况下，有这么性质：
乘法标准
8 mod 7 = 1
16 mod 7 = 2 64 mod 7 = 8 mod 7
加法标准 8 mod 7 = 1 10 mod 7 = 3
18 mod 7 = 4
第44页
故d|a。 • 所以d是a,b公因数 • 反之，假如d是a,b公因数，也能证出d
是b,c公因数
第12页
第一部分 同余相关
整除基本性质 欧几里德算法 扩展欧几里德算法 中国剩下定理
第13页
请写出12，30共有约数
第14页
请写出12，30共有约数 1,
第15页
请写出12，30共有约数 1, 2,
第37页
扩展欧几里德算法
扩展欧几里德算法(递归实现): int gcd(int a,int b) if b=0 then x←1 y←0 return a d←gcd(b,a%b) x'←y y'←x-[a/b]y x←x' y←y' return d

20 2019/4/14
第三类 技 巧 型
21 2019/4/14
先来看一个简单的题目 铺垫一下:
22 2019/4/14
1021 Fibonacci Again
题目分析：

能被3整除的整数的特点？ 如果两个数的和能被3整除，这两个数 有什么特点？ 关于能否被3整除，这两个数一共有多 少种组合？
第四类 纸老虎型
33 2019/4/14
HDOJ_1071 The Area
第一眼：傻了…
想一想
笑了…

36 2019/4/14
抛物线公式：y=ax^2+bx+c 已知三点 -〉a、b、c 系数
公式已知 - 〉如何求面积？ 会简单积分吗？
37 2019/4/14
第五类 AC基础型
38 2019/4/14

抱歉
如果平面上有n个点，并且每个点至少有2条 曲线段和它相连，就是说，每条曲线都是封 闭的，同时，我们规定： 1）所有的曲线段都不相交； 2）但是任意两点之间可以有多条曲线段。
如果我们知道这些线段把平面分割成了 m份， 你能知道一共有多少条曲线段吗？
42 2019/4/14
分析：从特殊到一般的方法
25 2019/4/14
回到正题
26 2019/4/14
Problem B: Number Sequence
题目特点：
这个题目是一个比较典型的ACM竞 赛题，尽管在真正的大赛中这个题目可 能算比较简单的，但在本次比赛中，本 题难度属于中等，可以说，能做出本题 的队伍基本都有二等奖以上。 但如果不认真分析，有可能会掉入 陷阱。
28 2019/4/14
Question:

2 How do recursive algorithms work?
递推算法通常由一个基本情况和一个递推关系组成。当问题达到基本情况时，递归过程 结束并返回结果。否则，递归算法将继续调用自身来解决较小的子问题。
3 What are some common examples of recursive algorithms?
Why are ACM递推 problems important?
ACM递推问题是计算机科学和编程中的重要部 分。通过解决这些问题，我们可以提高自己的 编程能力和算法思维，同时也可以应用递推算 法解决实际的问题。
递推算法基础知识
1 What is a recursive algorithm?
递推算法是一种通过不断调用自身来解决问题的算法。它可以将大问题分解成多个较小 的子问题，并通过解决子问题的方式来得到最终的解。
3 减少递归深度
通过优化递归算法的终止 条件和边界情况，可以减 少递归的深度，降低递归 算法的时间复杂度。
递推问题的时间复杂度分析
What is time complexity?
时间复杂度是用来衡量算法执行时间与输入规模之间关系的一种指标。它可以帮助我们评估 算法的效率和性能。
How to analyze the time complexity of a recursive algorithm?
总结与展望
1 递推算法的重要性
递推算法在算法设计和问题求解中起着重要的作用。通过掌握递推算法的基本知识和常 见求解方法，我们可以更好地解决问题并优化算法。
2 未来的发展方向
未来，随着计算机科学和技术的进步，递推算法将继续发展和创新，为解决更复杂的问 题提供更高效的求解方法。
《ACM递推求解》PPT课 件

a[k++]=i;
}
授课：XXX
5
参考源代码
while(scanf("%d",&n)==1) {
printf("%d: ",n); for(i=0;i<k;i++) {
if(a[i]<=n) printf("%d ",a[i]);
} printf("\n"); } return 0; }
授课：XXX
授课：XXX
2
输出描述
对于每个整数n，输出所有不大于n的完数。每个整 数n的输出由n引导，跟上冒号，然后是由空格开道 的一个个完数，每个n的完数列表应占独立的一行。
输入样例
100
5000 输出样例
100： 6 28 5000： 6 28 496
授课：XXX
3
题目分析
如果针对每个整数都搜索一次 完数，时间会花费较多，由于 完数较少，可以先找出10000 以内的所有完数，然后再针对 n查表。
{
if (bp[i]) //i是素数
{
p[pCnt++] = i;
for (j = i + i; j <= Max; j += i) //依次筛掉i的倍数
bp[j] = false;
}
}
}
授课：XXX
26
刚才的发言，如 有不当之处请多指
正。谢谢大家！
2021/3/9
27
}
return 0;
}
授课：XXX
11
五位以内的对称素数
题目内容
判断一个数是否为对称且不大于五位数的素数。