例题佳佳的困惑.ppt

例题：佳佳的困惑,给出一个数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，使得其综合比例(c1c2c3cm)/(d1d2d3dm)为给定值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个数，分解质因数，并对每个质因数出现次数的奇偶性进行记录。设xi=0或1代表是否使用第i个数。可以列出一个关于xi(1=i=m)的位方程组（乘积的所有质因数出现次数均为偶数）。解该方程组，检查最后有多少自变量，设有n个，那么结果应该是2n-1（除去空集）。时空复杂度均为O(M2),思考：传球游戏,N个人围圈玩传球游戏，开始时第一个人拿着球，每个人把球传给左手的第K个人。满足1KN/2。求K的最大值，使得第一个人重新拿到球之前，每个人都拿过球。,例题：无限赛跑,AB总长度为L车一从A出发，速度为u车二从B出发，速度为v走到端点立刻返回，无时间损失开车总时间tu,v,t都是正整数相遇多少次？,分析,第一种相遇:相向t(u+v)=(2k+1)L 第二种相遇:同向t|uv|=(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)=k1r是满足条件的最小正数r=L/gcd(u,v),分解因数,分解因数可以转换为求最小素因子(找到最小素因子后递归求解)分解素因数后得到惟一分解式sumpiki,可以求出约数个数,即所有ki+1的乘积(由乘法原理容易证明)方法一:试除法方法二:pollard-rho算法,思考：反素数,正整数n是一个反素数，如果这个数的约数个数超过比n小的任何数的约数个数。给定n(=2*109)，求不超过n的最大反素数数m,