众所周知，gcd(x, y) = gcd(y, x%y) 但怎么证明其正确性，既保证我们这么做得到的答案一定是最大公约数 今天，我就来证明一下。 首先，我们要知道两条推论： 若 a|b，则 ka|b; 若 a|b，c|b ，则 (a±b)|c; 当我们知道这两条推论后，我们还需要知道一件事情，如果 a≤b， b≤a，则 a=b; ...

1214 线段覆盖  题目描述 Description     给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部…

Balance Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 13761 Accepted: 8652 Description Gigel has a strange "balance" and he wants to poise it. Actually, the devic…

题目描述 Description 有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 ...

放苹果 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 31107 Accepted: 19624 Description 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。 Input 第一行是…

Maze Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 3846 Accepted: 1220 Description Acm, a treasure-explorer, is exploring again. This time he is in a special maze…

题目描述 Description 有编号为1至n的n个同学一起去探险,现在把他们分成k个小组,每个小组完成一项探险任务。分组时,如果第i人与第j人分在同一组(i<j),则他们之间的所有人(第i+1,i+2,…,j-1个)也必须在同一个小组中。 ...

题目描述 Description 小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n 个矿石，从1到n 逐一编号，每个矿石都有自己的重量wi 以及价值vi。检验矿产的流程是：见图 若这批矿产的检验结果与所给标准值S 相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的…

题目描述 Description 果园里有n颗果树，每棵果树都有一个编号i(1≤i≤n)。小明已经把每棵果树上的果子都摘下来堆在了这棵树的下方，每棵树下方的果子体积为ai。 ...

8468:单词序列 总时间限制:1000ms内存限制:1024kB 描述 给出两个单词（开始单词和结束单词）以及一个词典。找出从开始单词转换到结束单词，所需要的最短转换序列。转换的规则如下： 1、每次只能改变一个字母 2、转换过程中出现的单词(除开始单词和结束单词)必须存在于词典中 ...