模同余与公约数题解.pdf

《模同余与公约数题解.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、POJ3292【基础】题目大意：对于C语言的for(i=A;i!=B;i+=C)循环语句，问在k位存储系统中，使用无符号型整数循环几次才会结束。注意，如果i>2^k-1，那么由于越界，i会变成i-2^k-1。输入：有若干组测试数据，每一组包含一行，有四个整数A、B、C和k。处理到文件结束。输出：对于每一组测试数据，输出一行：若在有限次内结束，则输出循环次数，否则输出“FOREVER”。题解：容易得到这是一个单变元模线性方程Cx=(B-A)(mod2^k)，记C=a，B-A=b，2^k=n，得到单变元模线性方程的标准形式ax=b(modn)。由于数学原理比较冗长，建议

2、上网搜索或者找线性代数的书或者参考《算法导论》，我不在此赘述，仅说一下解法。记d=gcd(a,n)，先使用扩展欧几里德求出ax+ny=d的解（扩展欧几里德可以求出ax+by=gcd(a,b)的解x、y）。如果b不能整除d则无解，否则modn意义下的解有d个，可以先求出最小的解然后不断加上n/d来得到。这里我们只需要直接取最小的一个正整数解就可以了。POJ2635【基础】题目大意：求正整数K(4<=K<=10^100)是否有一个素因子小于L(2<=L<=10^6)。输入：有若干组测试数据，每一组测试数据占一行。每一行有两个整数，第一个是K，第二个是L。当K=L=0时测

3、试数据结束。输出：对于每一组测试数据，如果存在一个素因子小于L，输出一行“BAD%d”，%d表示最小的一个素因子。如果没有这样的素因子，输出一行“GOOD”。题解：高精度求模。由于L的范围不大所以可以先打表把所有素数打出来.然后用高精度存L（我用的是1000000000进制），模余的时候相当于做除法一步一步往下模余即可。POJ2305【基础】题目大意：给出两个在b（2<=b<=10）进制下的非负整数p和m，求p模m在b进制下的值。p最多有1000位，m最多有9位。输入：有若干组测试数据，每一组测试数据占1行。每一行第一个整数是b，当b=0时测试数据结束，否则后面有两

4、个空格分隔的整数p和m。输出：对于每一组测试数据，输出一行，包含一个整数。题解：这题应该属于进制转换和大数的模运算的结合。思路是直接把m、p都转换到10进制下进行模余，然后再可以肯定m可以直接用一个int存下来。然后可以用高精度保存m再进行模，类似于POJ2635一样，或者在将m转换为10进制的过程中直接进行模运算。道理很简单，因为(A*B)%C=((A%C)*(B%C))%C，(A+B)%C=((A%C)+(B%C))%C（这两条是大数模运算的基础）。POJ1006【中等】题目大意：人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天

5、和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。我们想知道何时三个高峰落在同一天。对于每个周期，给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。给出一个一年中的一个天数D，求这个天数以后下一次出现三个高峰同一天的天数是给出的天数后的第几天。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2。输入：有若干组测试数据。每一组测试数据有四行，包括四个整数p、e、i和d。p,e,i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计

6、算）。d是给定的时间，可能小于p、e、或i。所有给定时间是非负的并且小于365,所求的时间小于21252。当p=e=i=d=-1时，输入数据结束。输出：每一组测试数据输出一行，格式为“Case%d:thenexttriplepeakoccursin%ddays.”，第1、2个%d分别表示测试数据编号（从1开始）和所求的天数差。题解：这题需要用到中国剩余定理来解模方程组。我们在几代中学过这个定理的多项式版本，即通用版，我先简要地叙述一次，证明此处略去请各位自己查：对于方程组f≡ri(modgi)，其中fi、ri、gi为多项式，其中gi是互质的。记G=g1*g2……gn

7、，Gi=G/gi。由Bezout等式（若多项式f、g互素，必存在多显示u、v令uf+vg=1成立），知道必有ui*gi+vi*Gi=1，则sigma(i=1ton,ri*vi*Gi)为满足要求的f的最低次数的解。当多项式变成整数时，我们改一下叙述：对于方程组x≡ri(modgi)，其中gi是互质的。记G=g1*g2……gn，Gi=G/gi。存在yi，令Gi*yi≡1(modgi)，则x的最小值为sigma(i=1ton,ri*Gi*yi)。由于x的和式中除了第i项，其他各项都是gi的倍数，所以x是满足要求的。而在求解Gi*yi=1(modgi)时，等于求解(Gi