例题：佳佳的困惑.pptVIP

* * 例题：佳佳的困惑 给出一个数N，含数字1、2、3、4，把N的所有数字重新排列一下组成一个新数，使它是7的倍数。 分析 把数字1、2、3、4从中抽出，然后把其他数字按照原顺序排列（事实上，怎么排列都无所谓）组成自然数w w*10,000整除7取余有7种可能，即是为0、1、2、3、4、5、6。这时如果能用数字1、2、3、4排列出7个数，使它们整除7取余的值分别为0、1、2、3、4、5、6，把这个4位数接在w后面即为问题的解。 例题：街道数 找所有的(n, k)数对, 满足: 1+2+..+(n-1)=(n+1)+(n+2)…+k 输出按k排序的前10个 分析 整理得: n(n-1)=(k-n)(n+k+1) 化简得: k2+k-2n2=0, 即n2=k(k+1)/2 由于k和k+1互素, 因此 要么k是完全平方数 要么k/2是完全平方数 分别设k=m2和2m2, 枚举m 例题：齿轮 假设有三种齿轮：6齿，12齿，30齿。想要实现4 : 5的比例，一种可行方案如下： 给定可用的齿轮（每种均有无穷多），设计一系列传输c1 : d1, c2 : d2, …, cm : dm，使得其综合比例(c1c2c3…cm)/(d1d2d3…dm)为给定值a:b。 给定齿轮的齿数为5到100，a和b不超过10000。 分析 使用惟一分解定理, 单独考虑各个素因子 c1 = p1a1*p2*a2*… c2 = p1b1*p2*b2*… … 则c1x*c2y=p1(x*a1+y*b1) *p2(x*a2+y*b2) 目标a:b = p1z1 * p2z2 … x*a1+y*b1=z1; x*a2+y*b2=z2 例题：破解RSA 给定M个数，它们的质因子在前T个质数范围内。求这M个数组成集合的满足如下条件的非空子集个数：子集中所有数的积为完全平方数。 分析 首先将读入的M个数，分解质因数，并对每个质因数出现次数的奇偶性进行记录。 设x[i]=0或1代表是否使用第i个数。可以列出一个关于x[i](1=i=m)的位方程组（乘积的所有质因数出现次数均为偶数）。 解该方程组，检查最后有多少自变量，设有n个，那么结果应该是2n-1（除去空集）。 时空复杂度均为O(M2) 思考：传球游戏 N个人围圈玩传球游戏，开始时第一个人拿着球，每个人把球传给左手的第K个人。满足1≤K≤N/2。求K的最大值，使得第一个人重新拿到球之前，每个人都拿过球。 例题：无限赛跑 AB总长度为L 车一从A出发，速度为u 车二从B出发，速度为v 走到端点立刻返回，无时间损失 开车总时间t u, v, t都是正整数 相遇多少次？ 分析 第一种相遇: 相向t?(u+v)=(2k+1)L 第二种相遇: 同向t?|u?v|=(2k+1)L 重复: 在端点相遇? 第一次同时到达端点时刻为r 到达不同端点? 到达同一端点 A和B分别运动2k1L和(2k2+1)L 下一次到达哪里? 不同端点?又同时到达此端点?同时到达另一端点? t=(2k+1)r 分析 如何求r? r是L/u的整数倍(u*r = k1L) r是L/v的整数倍 r是L/gcd(u,v)的整数倍 u/gcd(u,v) * r/(L/gcd(u,v)) = k1 r是满足条件的最小正数 r=L/gcd(u,v) 分解因数 分解因数可以转换为求最小素因子(找到最小素因子后递归求解) 分解素因数后得到惟一分解式sum{piki}, 可以求出约数个数, 即所有ki+1的乘积(由乘法原理容易证明) 方法一: 试除法 方法二: pollard-rho算法 思考：反素数 正整数n是一个反素数，如果这个数的约数个数超过比n小的任何数的约数个数。 给定n(=2*109)，求不超过n的最大反素数数m