数论例题(上传版).doc

例1：给三个数字t,a,b(都比2147483647小)，当(t^a-1)/(t^b-1)是整数且小于100位数时输出其值。
Sample Input
2 9 3
2 3 2
21 42 7
123 911 1
Sample Output
(2^9-1)/(2^3-1) 73
(2^3-1)/(2^2-1) is not an integer.
(21^42-1)/(21^7-1) 18952884496956715554550978627384117011154680106
(123^911-1)/(123^1-1) is not an integer.

分析：
1）t=1 è 分母为0.
2）a=bè 等于1.
3）if(a%b!=0) è 不能整除.
实际上，若(t^a-1)/(t^b-1)= n, 则b|a
考查等比数列求和公式：a1+a2+……+an=a1(qn-1)/(q-1)
所以b|a，令x=t^b, a/b=m, m是正整数，
(t^a-1)/(t^b-1)=(x^m-1)/(x-1)=x^(m-1)+x^(m-2)+x^(m-3)+….+1
∵x^(m-1) > x^(m-2)+x^(m-3)+….+1
∴x^(m-1) 加上 x^(m-2)+x^(m-3)+….+1 最多进一位数。
Log10(x^(m-1))=log10(t^(a-b))=(a-b)*log10(t)
∴if((a-b)*log10(t)<99),小于100位数

例2：Poj1061 青蛙的约会
Time Limit: 1000MS Memory Limit: 10000K
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

Input
输入只包括一行5个整数x，y，m，n，L，其中x≠y <2000000000，0 < m、n < 2000000000，0<L< 2100000000。
Output
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
Sample Input
1 2 3 4 5
Sample Output
4

分析：设过s步后两青蛙相遇，则必满足以下等式：
　　　　(x+m*s)-(y+n*s)=k*l (k=0,1,2....)
　　变形得：　(n-m)*s+l*k=x-y

　　只要上式存在整数解，则两青蛙能相遇，否则不能。

例3：Poj1142 Smith Numbers
Time Limit: 1000MS Memory Limit: 10000K
Smith's telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:
4937775= 3*5*5*65837
The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42,and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+ 3+7=42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers.
As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition.
Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!

Input
The input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits.
The input is terminated by a line containing the number 0.

Output
For every number n > 0 in the input, you are to compute the smallest Smith number which is larger than n,and print it on a line by itself. You can assume that such a number exists.
Sample Input
4937774
0
Sample Output
4937775

分析：合数的质因数分解问题。设当前数为num，每找到num的一个质因数m，就除以m，将num化小重置，减少循环次数。

例3：Poj2407 Relatives （欧拉函数）
Time Limit: 1000MS Memory Limit: 65536K
Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x>1, y>0, z>0 such that a=xy and b=xz.
Input
There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
7
12
0

Sample Output
6
4

分析：给定一个数(小于1,000,000,000),求与它互质的数的个数。
从2开始到n-1循环查找，速度？可应用欧拉函数，每找到一个质因数就乘进来。

思考题：Poj2447 RSA
Time Limit: 3000MS Memory Limit: 65536K

RSA is the best-known public key encryption algorithm. In this algorithm each participant has a private key that is shared with no one else and a public key which is published so everyone knows it. To send a secure message to this participant, you encrypt the message using the widely known public key; the participant then decrypts the messages using his or her private key. Here is the procedure of RSA:

First, choose two different large prime numbers P and Q, and multiply them to get N (= P * Q).
Second, select a positive integer E (0 < E < N) as the encryption key such that E and T= (P - 1) * (Q - 1) are relatively prime.
Third, compute the decryption key D such that 0 <= D < T and (E * D) mod T = 1. Here D is a multiplicative inverse of E, modulo T.

Now the public key is constructed by the pair {E, N}, and the private key is {D, N}. P and Q can be discarded.

Encryption is defined by C = (M ^ E) mod N, and decryption is defined by M = (C ^ D) mod N, here M, which is a non-negative integer and smaller than N, is the plaintext message and C is the resulting ciphertext.

To illustrate this idea, let’s see the following example:
We choose P = 37, Q = 23, So N = P * Q = 851, and T = 792. If we choose E = 5, D will be 317 ((5 * 317) mod 792 = 1). So the public key is {5, 851}, and the private key is {317, 851}. For a given plaintext M = 7, we can get the ciphertext C = (7 ^ 5) mod 851 = 638.

As we have known,for properly choosen very large P and Q, it will take thousands of years to break a key, but for small ones, it is another matter.

Now you are given the ciphertext C and public key {E, N}, can you find the plaintext M?
Input
The input will contain several test cases. Each test case contains three positive integers C, E, N (0<C<N, 0<E<N, 0<N<2^62).
Output
Output the plaintext M in a single line.
Sample Input
638 5 851
Sample Output
7

这题可以说是数论部分的一个大综合题，因为它将算法导论上数论这部分的知识点全部包含了进来，包括gcd,扩展gcd,模线性方程，a^b mod c,miller-rabin素数测试，pollard_rho质因数分解等等，把这题搞定了说明你对算法导论的数论部分已经可以做到熟练掌握了。
简要介绍一下RSA算法加密解密的过程：
首先生成两个大的素数P,Q,乘起来得N=P*Q.然后算出N的欧拉函数Phi(N)= (P-1)*(Q-1).然后取一个范围在[1,phi(N)]中且与phi(N)互质的正整数E.它就是所谓的公钥。得到公钥之后，再算出E关于phi(N)的逆元D,即E*D mod phi(N)=1.这个D就是私钥。在得到这些数据以后，P,Q被丢弃，E,N做为公钥被公开，D做为私钥被解密人私人保存。

下面看一下如何用公钥和私钥对数据进行加密解密。
假设有一个明文M,那么它所对应的密文就是C=M^E mod N.
如果我们现在得到一个密文C,那么它所对应的明文就是M=C^D mod N
也就是说，任何人都可以用公钥对数据进行加密，但是只有拥有私钥的人才可以对数据进行解密。

那么RSA算法为什么不易被破解呢？从解密的过程来看如果你能够知道D那么你就能解密数据。而E,D是逆元关系，要求出D,需要知道phi(N)，由于N非常之大，普通的做法是从1开始枚举到N-1，计算和N互质的元素个数。可是N可以是几百位到上千位的数字，普通的计算机只能在1s内算到10^8量级，显然是不可能破解的。唯一有可能的方法基于大素数分解，如果你能将N分解成P*Q的乘积。那么就可以直接利用公式phi(N)=(P-1)*(Q-1)绕开暴力求解欧拉函数的过程，从而实现RSA的破解。

这道题就是模拟这个破解过程，下面来说说具体的做法：
1.首先用miller-rabin,pollard_rho做大整数的质因数分解，得到两个素数P,Q，pollard_rho的复杂度在N^0.25次方，那么一个64位的整数 要计算的次数为 2^64^0.25=2^16 =65536次，可以瞬间出解。
2.求出phi(N)=(P-1)*(Q-1)
3.然后用ext_gcd求出E关于phi(N)的逆元。
4.用得到的私钥对数据C进行解密即可。

对这题而言，仅仅完成上述步骤还是不够的。因为N达到2^62次方，即使是使用无符号long long ,也很容易因为出乘法操作而溢出。这也是网上说要避免使用扩展欧几里德的原因。其实实现的时候，我们可以自己写一个特殊的乘法（内部用加法实现），由于使用的无符号的long long ，第64位刚好可以用来保存两个数加过之后的进位位，再模除又可以保证其在2^62范围内，即可避免溢出。