-
最大公约数 --- 辗转相除法
a = ka * i + a1 a % i = a1
b = kb * i + b1 b % i = b1
(a + b) % i = (a1 + b1) % i -------> (a % i ) + (b % i) = (a + b) % i
gcc(a, b) ---> gcc(b%a, b)
#include <bits/stdc++.h> using namespace std; int gcc(int a, int b) { if(a==0) return b; return gcc(b%a, a); } int main() { int a, b; cin>>a>>b; cout<<gcc(a, b); return 0; } -
最小公倍数
a与b的最小公倍数 = a * b / gcc(a, b)
-
求素数问题
如：求第100002个素数是多少？
可通过筛法解决。
2, 3, 5, 7, 11.....
2的倍数的都不是素数...3的倍数的都不是素数，以此类推，一直到10。
通过一个数组来记录一个数是不是素数，如：b[2] = 1，表示数字2是素数。b[4] = 0，表示数字4不是素数。
-
糖果问题-买不到的数目
设有把水果糖包成4颗一包和7颗一包的两种。买糖的时候只能买这两种的组合，当然有一些数目是无法组合出来的，比如要买10颗。在这种情况下，最大不能买到的数量是17，大于17的任何数字都可用4和7组合出来。
输入：两个正整数，表示每种包装中糖的数目。
输出：一个正整数，表示最大不能买到的糖数。
解法：搜索能连续买到的糖的数目，当连续数目等于最小包装的时候，最大不能买到的糖数等于这个数-最小包装数。
#include <bits/stdc++.h> using namespace std; bool f(int i, int a, int b) { if(i%a==0 || i%b==0) return true; while(i>=a) { if(i%a==0) return true; i =i -b; } return false; } int se(int a, int b) { int mmin = min(a, b); int n = 0; for(int i=0 ; ; i++) { if(f(i, a, b)) n++; else n = 0; if(n == mmin) return i - mmin; } } int main() { int a, b; cin>> a >>b; cout<<se(a, b)<<endl; return 0; } -
博弈论问题：尼姆游戏
可以将每个数字用二进制表示出来，右对齐。要保证每列出现的1的个数是偶数。
算法初探：整数的基本性质
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 计算机二级C语言上机题库（南开版） 1.m个人的成绩存放在score数组中，请编写函数fun,它的功能是：将低于平...
- 回溯算法 回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并...
