初等数论[一] 经典.pptVIP

初等数论的概念;初等数论的概念;初等数论的概念;初等数论的概念;初等数论的概念;欧几里德算法;欧几里德算法;欧几里德算法扩展;欧几里德算法扩展;欧几里德算法扩展;欧几里德算法扩展;Afamousmathpuzzle(toj2219)

题目叙述：

有n个壶，和一个含有无穷多水的水源．每次我们只能：

１．把其中一个壶灌满．

２．把其中一个壶倒空．

３．把一个壶中的水倒入另一个壶中，直到一个壶为空或者另一个壶已经满了为止．

给定一个体积Ｗ，问能否经过若干次倒水后使得最终只有一个壶中只剩下Ｗ升水？;Afamousmathpuzzle(toj2219);Afamousmathpuzzle(toj2219)

Input:

首先输入水壶的个数n和需要达到的体积W,然后输入n个整数，分别代表n个水壶的容量.

n=0w=0输入结束.

Output:

当体积W最终能够实现的时候，输出YES,否则输出NO.;Afamousmathpuzzle(toj2219);Afamousmathpuzzle(toj2219)

要使n个水壶能倒出w体积的水，则必须符合以下两个条件:

１．至少有一个水壶的容量大于或等于w.

２．假设p是n个水壶容量的最大公约数，那么w必须p的倍数．;Afamousmathpuzzle(toj2219);CLooooops(toj2297)

题目叙述:

有以下C语言的循环，

for(variable=A;variable!=B;variable+=C)

statement;

假如所有运算都是在k位无符号数的范围内进行，即如果超出范围，则用2^k取余．

求直到循环停止，statement语句被执行了多少次．;CLooooops(toj2297);CLooooops(toj2297);CLooooops(toj2297)

假设t=2^k,statement执行p次后，循环结束,则有:

(a+pc)%t=b

也即:

a+pc=wt+b

其中w为某一整数．

整理得:

pc+wt=b-a;CLooooops(toj2297)

pc+wt=b-a

在这个等式中，c,t,b,a是已知的，p是我们要求的，w是某一个整数．

由欧几里德算法的扩展我们可以得到:

c’c+t’t=gcd(c,t)

如果b-a不能被gcd(c,t)整除，则上述等式无解；否则p=(b-a)/gcd(c,t)*c’.;CLooooops(toj2297);StrangeWaytoExpressIntegers

(pku2891)

题目叙述:

有一种新的表示非负整数的方法，选择k个不同的正整数a1,a2,…,ak,对于任意一个非

负整数m，我们可以用k个数对(ai,ri)去表示，其中ri=m%ai．如果适当地去选择a1,a2…,ak，m可以被唯一确定．

已知m去计算数对是十分容易的，现在我们要根据数对去求m的值．;StrangeWaytoExpressIntegers

Input:

首先输入数对的个数k,然后输入k个数对(ai,ri).

Output:

输出满足条件的非负整数m，如果存在多个m，输出最小的那个.如果m不存在，则输出-1.;StrangeWaytoExpressIntegers

SampleInput:

2

87

119

SampleOutput:

31;StrangeWaytoExpressIntegers;StrangeWaytoExpressIntegers;StrangeWaytoExpressIntegers

也就是说m%a1=r1m%a2=r2与m%lcm(a1,a2)=m’%lcm(a1,a2)是等效的，所以我们一个用一个数对(lcm(a1,a2),m’%lcm(a1,a2))去替换原来

的两个数对(a1,r1),(a2,r2);

同上个题相同，求得的m’必须加上或者减去若干个lcm(a1,a2,…,ak)直至非负且最小才是最终的结果.