第16章 数论问题 20001(=9,10001(=5,167)=22. r=(29-1)(35-1)(225-1))=18*10*12)=14

S)=r*9)=14*9)=10, 200410000的所有因子和对29取模的结果是10

int mod29(int x) {

for(r=0;r<=x;++r)

{f=f*(r==x?2:4)); t=t*3); d=d*22);}

//f表示22x+1的值 //t表示3x+1的值

//d表示167x+1的值

r=(f-1)*(t-1)*(d-1)); //S=r/332,r的值 return r*9); //S)=r*9) }

int main(){

while(scanf(\printf(\}

16.2.2 〖案例3〗2x mod n=1

给定一个整数n，求一个最小的整数x，使得2x mod n = 1。

每行一个正整数n,.(0 ? n ? 231-1)

如果最小的正整数存在，输出一行2^x mod n = 1，其中的x和n用输入的n值和最小的x值代替；否则，输出一行2^? mod n = 1。

2 5

2^? mod 2 = 1 2^4 mod 5 = 1

本题首先想到的可能是暴力搜索，从x=1开始，逐步加大x，找到使得2^x mod n = 1

·235·

ACM程序设计培训教程

的x就输出。但考虑到n比较大，满足2^x mod n = 1的x可能也很大，所以直接求解的方法不行。

根据Euler定理，当p是奇数时，a?(p)modp?1，而?(p)?p??1?p????1?p?????1?p??，因

1??2?k???此，2?(n)modn?1，?(n)似乎就是答案。但题目要求的是满足2^x mod n = 1最小的x，所

63

以在某些情况下?(n)?x，例如，n=7,?(n)=6,2 mod 7=1,但2 mod 7=1,最小的x是3。但可以推导出x一定是?(n)的因子：如果x是满足2^x mod n = 1最小的x,假设x不是?(n)的因子，则r=?(n) mod x,r大于0（因为假设x不是?(n)的因子），同时r

rx2?(n)modn?1，而且2modn?1，所以2modn?1，则存在一个比x还小的正整数，使得2rmodn?1，与假设x是最小矛盾。所以x一定是?(n)的因子。

所以解题步骤是： 1．求解x=?(n);

2．找出?(n)的所有素因子pi;

3．让x=x/pi,直到2x mod n?1或pi不能整除x.如果2x mod n?1，x=x*pi; 4．重复3，直到所有的素因子pi都经过3处理； 5．x就是满足2^x mod n = 1最小的x。

因为求phi(n)和找出phi(n)的所有素因子pi都需要知道在215.5?46340内的所有素数，所以在问题求解前，先作预处理：利用筛法将所有小于46340的素数求出来。

求2xmodn采用上一节介绍的求abmodm的方法。

int prime[5000], nB_prime; //根据素数分布定律，小于46340的素数约5000个 sieve() //采用筛法求所有小于46340的素数 {short p[23170];

//求所有小于46340的素数，因为大于2的偶数都不是素数，所以筛法只对应所有的大于1小于46340的奇数

//如果p[i]=1表示2*i+3是素数,否则p[i]=0表示2*i+3不是素数。 for(i=0;i<23170;++i) p[i]=1; for(i=0;i<106;++i) if(p[i])

//初始化，假定所有奇数都是素数 //106=sqrt(46340)/2-3

?1??1??1? for(k=(i<<1)+3,j=(k+1)*(i+1)-1;j<23170;j+=k) p[j]=0;

for(prime[i=j=0]=2;i<23170;++i) if(p [i])

prime[++j]=(i<<1)+3; nb_prime=j+1;}

int ttn(int i,int n){ __int64 t=2,r=1; while(i) { if(i&1)

//函数计算2i mod n=?

//用64位长整型防止中间结果溢出,t?22,r?2i%n

i 236· ·

第16章 数论问题 r=t*r%n; t=t*t%n; i>>=1;} return r;}

int phi(int n) {

// 函数求?(n)

result=temp=n;k=sqrt(n);

for(i=0;prime[i]<=k&&i

if(!(temp%prime[i])) //如果prime[i]是n的因子 {do

temp/=prime[i];

while(!(temp%prime[i]));

result=result/prime[i]*(prime[i]-1); k=sqrt(temp);}

if(temp-1) //如果n的素数因子超过46340的范围 result=result/temp*(temp-1); return result;}

int main(){ sieve();

while(scanf(\

if(n<2||!(n&1)) { //如果n<2,或者n是偶数，无正整数解 printf(\ continue;}

x=temp=phi(n);

for(i=j=0;prime[i]<=k&&i

r[j++]=prime[i]; //r记录phi(n)的所有素数因子 if(j==0&&temp>1) r[j++]=temp;

for(i=0;i

while(x%r[i]==0&&(k=ttn(x,n))==1)

x/=r[i]; // result是phi(p)的因子 if(k!=1)

x*=r[i];}

printf(\}

16.3 素数测试

在解决数论问题时，常常需要知道哪些数是素数。所以检测某些数是否是素数，以及找出某些范围中的所有素数是数论问题中出现比较频繁的问题。

·237·

ACM程序设计培训教程

本节给出2个案例，一个是找出一定范围内所有素数的方法，即所谓筛法；另一个是判断一个数是否素数的概率算法：Miller测试。

16.3.1 〖案例4〗素数距离

数论，数学的一个分支，是研究数的性质。其中素数领域的研究几千年来一直吸引着人们的注意力。一个素数是除了自己和1以外没有别的整数可以整除它的数。最开始的素数有2，3，5，7等，但很快将变得很稀疏。一个有趣的问题是素数在不同范围内的密度。相邻素数是两个素数，他们之间没有别的素数。如2，3就是相邻素数。

你的程序将输入2个数，L和U (1<=L< U<=2,147,483,647)，你要找出2个相邻素数C1和C2 (L<=C1< C2<=U)是距离最小的。（也就是说C2-C1最小）。如果最小距离的相邻素数不止一对，选择最初的。你还需要找出2个相邻素数D1 和D2 (L<=D1< D2<=U) 是距离最大的（同样在有多对的情况选择最初的）。

每行输入2个正整数， L和U， L < U。L和U的差不超过1,000,000。

对于每组L和U，如果没有相邻素数输出一行“There are no adjacent primes .” ，否则输出给定的两对相邻素数。

2 17 14 17

2,3 are closest, 7,11 are most distant. There are no adjacent primes.

解决本题的基本思路是：在给定范围内，找出其间的所有素数，然后再把素数间的最大距离、最小距离求出来。

所以解决这个题首先需要将在[L,U]范围的所有素数找出来。在给定范围内，找出其间的所有素数，最常用的方法就是筛法。

所谓筛法就是：开始假设所有的范围内的数都是素数，然后将所有素数的倍数（肯定不是素数）筛掉，经过数轮筛选，剩下来的就是素数。

实际作筛法时，考虑到所有大于2的偶数都不是素数，为了节省存储空间，可以只对给定范围内的所有奇数进行筛选即可。

具体到本题，因为数据区间的上界到达21亿，不能将所有小于21亿的素数存下来。只能

238· ·