數(shù)論問題 (1)

1、數(shù)論問題,Lecture by Hao Wu,常見的數(shù)論問題,1.數(shù)的冪運(yùn)算 2.歐拉定理的應(yīng)用 3.素數(shù)測試4.Pell方程5.其它,案例1：模的運(yùn)算,Time Limit: 1000ms Special Time Limit:2500ms Memory Limit:32768KB,描述,人與人是不同的,有些人喜歡閱讀滿是女孩子的雜志，有些人喜歡在地下室引爆炸彈，而還有一些卻喜歡一些麻煩的數(shù)字游戲。比如ESSE論壇的一次活

2、動：每個人選擇兩個數(shù)字Ai和Bi寫在紙上，其他人不能看見。過了一段時間后，每個人說出自己紙上的數(shù)字，然后每個人的目標(biāo)是求出所有的AiBi的和模M的值，最先算出結(jié)果的，就是勝利者。作為一個程序員，你當(dāng)然有辦法編一個程序，以最快的速度算出結(jié)果，贏得比賽。,輸入,輸入包含Z組測試數(shù)據(jù)，輸入第一行只包含數(shù)字Z。隨后是測試數(shù)據(jù)：第一行是一個數(shù)字M(1≤M≤45000)。第二行是數(shù)字H（1≤H≤45000）表示參加游戲的人數(shù)。接下來H行，每行兩

3、個數(shù)Ai和Bi（1≤Ai，Bi≤231）,輸出,對于每組測試數(shù)據(jù)，輸出以下表達(dá)式的值：(A1B1+A2B2+...+AHBH)modM.,輸入樣例,31642334455636123123748593029382171318132,輸出樣例,21319513,解題思路（1）,取模運(yùn)算可以與加、減、乘、乘方交換次序；(a+b)%m=a%m+b%ma*b%m=(a%m)*(b%m)ab%m=(a%m)b,

4、解題思路（2）,有一類常見的運(yùn)算，就是求形如的值，一般情況下，我們可以用冪的定義來做：通過乘法的倍乘來實現(xiàn)，需要做b次乘法和模運(yùn)算。如果b比較大時，這樣的方法就不行了，本節(jié)介紹一種只需要O(log2b)次乘法和模運(yùn)算的方法。,解題思路（3）,首先將指數(shù)變成二的冪次和的形式。如5=1+4=20+22，11=1+2+8=20+21+23。如果b可以表示為的形式，那么ab可以表示為,,解題思路（4）,表面上看這樣的表達(dá)式更復(fù)雜了，但注意到上面

5、的表達(dá)式的乘積項不超過(log2b)，同時，形如（i=0,1….）有如下的遞推式：,,解題思路（5）,后項可以通過前項的平方來得到。所以可以先的值求出來，不超過(log2b)次乘法。,,,核心代碼及解釋 （1）,voidcal(unsigned*r,longunsigneda,unsignedm){//計算a的2j次方對m取模的結(jié)果,用數(shù)組r保存r[0]=a%m;for(i=1;i<32;++i)r[i]=(long)r[

6、i-1]*r[i-1]%m;//ri+1=ri*ri},核心代碼及解釋 （2）,unsignedcalc(unsignedm,longunsigneda,longunsignedb){//函數(shù)計算ab%m的值intbl[32],r[32];//bl是b的二進(jìn)制結(jié)果，r[i]=a的2j次方對m取模的結(jié)果cal(r,a,m);//計算r[i]while(b){//將b用二進(jìn)制形式表示,結(jié)果保存在bl中bl[i++]=b%2;b

7、>>=1;}for(j=0,k=1;j<i;++j)//計算乘方，時間復(fù)雜度為i=O(log2b)if(bl[j])//如果b對應(yīng)二進(jìn)制位bj為1,則對應(yīng)的rbj在冪的乘積表達(dá)式中，否則不在k=k*r[j]%m;Return k;},核心代碼及解釋 （3）,Int main(){scanf("%d",&z);while(z--){scanf("%u%d",&

8、amp;m,&i);for(j=s=0;j<i;++j){scanf("%lu%lu",&a,&b);s=(s+calc(m,a,b))%m;}//計算AjBj的值，并將其和求出來，結(jié)果用變量s保存printf("%u\n",s);}},歐拉定理1,如果p是素數(shù)，則對任意的a，有,,歐拉定理2,如果p不是素數(shù)，則對任意的a，有,,,p1,p2,…,pk是p的所

9、有素數(shù)因子,案例2：快樂2004,Time Limit: 1000msSpecial Time Limit:2500msMemory Limit:32768KB,描述,考慮到一個正整數(shù)X，S是所有2004X的因子的和，你的目標(biāo)是求出S除以29的余數(shù)?？纯碭=1的例子，20041的所有因子為1,2,3,4,6,12,167,334,501,668,1002和2004，因此S=4704，而4704 mod 29 =6。,輸入,輸入有多

10、個測試序列，每個測試序列一行一個正整數(shù)X，(1<=X<=10000000)。X=0表示輸入結(jié)束，并且不需要處理。,輸出,對每個測試序列，輸出一行就是S除以29的余數(shù)。,輸入樣例,1100000,輸出樣例,610,解題思路（1）,題目要求的是（2004X）的因子和對29取模的結(jié)果求某個數(shù)A的所有因子和，首先將該數(shù)分解： 其中p1,p2,...,pn都是素數(shù)，則A的任意因子可以表示為：其中0?i1?r1,....0?

11、in?rn,,,,解題思路（2）,如：2004=22*3*167，則,,,解題思路（3）,,,,解題思路（4）,X還很大( )，根據(jù)Euler定理,,,,,所以首先將X對28取模，x=X%28是取模的結(jié)果，x就很小了(0?x<28，有了這點，輸入的X再大也沒關(guān)系)，簡單計算就可以得到r的值,解題思路（5）,,,,,,解題思路（6）,當(dāng)X=10000時，計算200410000=220000*310000*167

12、10000的所有因子和對29取模的結(jié)果,,20001%28=9,10001%28=5,167%29=22.r=(29-1)(35-1)(225-1)%29=18*10*12%29=14S%29=r*9%29=14*9%29=10, 2004100000的所有因子和對29取模的結(jié)果是10,核心代碼及解釋 （1）,int mod29(int x) {for(r=0;r<=x;++r){f=f*(r==x?2:4)%29;

13、 //f表示22x+1的值t=t*3%29; //t表示3x+1的值d=d*22%29;} //d表示167x+1的值r=(f-1)*(t-1)*(d-1)%29; //S=r/332,r的值return r*9%29; //S%29=r*9%29},核心代碼及解釋 （2）,int main(){while(scanf("

14、%d",&x),x)printf("%d\n",mod29(x%28));},案例3：2x mod n=1,Time Limit: 1000ms Special Time Limit:2500ms Memory Limit:32768KB,描述,給定一個整數(shù)n，求一個最小的整數(shù)x，使得2x mod n = 1,輸入,每行一個正整數(shù)n,.(0 ? n ? 231-1),輸出,如果最小的正整數(shù)存

15、在，輸出一行2^x mod n = 1，其中的x和n用輸入的n值和最小的x值代替；否則，輸出一行2^? mod n = 1,輸入樣例,25,輸出樣例,2^? mod 2 = 12^4 mod 5 = 1,解題思路（1）,本題首先想到的可能是暴力搜索，從x=1開始，逐步加大x，找到使得2^x mod n = 1的x就輸出。但考慮到n比較大，滿足2^x mod n = 1的x可能也很大，所以直接求解的方法不行。,解題思路（2）,Eule

16、r定理,,,解題思路（3）,x一定是phi(n)的因子,,解題步驟,1．  求解x=phi(n);2．  找出phi(n)的所有素因子pi;3．  讓x=x/pi,直到2x mod n?1或pi不能整除x.如果2x mod n?1，x=x*pi;4．  重復(fù)2；x就是滿足2^x mod n = 1最小的x。,解題思路（4）,因為求phi(n)和找出phi(n)的所有素因子pi都需要知道在2

17、15。5?46340內(nèi)的所有素數(shù)，所以在問題求解前，先作預(yù)處理：利用篩法將所有小于46340的素數(shù)求出來,核心代碼及解釋 （1）,int prime[5000], no_prime; //根據(jù)素數(shù)分布定律，小于46340的素數(shù)約5000個sieve() //采用篩法求所有小于46340的素數(shù){short p[23170]; //求所有小于46340的素數(shù)，因為大于2的偶數(shù)都不是素數(shù)，所以篩法只對應(yīng)所有的大

18、于1小于46340的奇數(shù)//如果p[i]=1表示2*i+3是素數(shù),否則p[i]=0表示2*i+3不是素數(shù)。 for(i=0;i<23170;++i)p[i]=1; //初始化，假定所有奇數(shù)都是素數(shù)for(i=0;i<106;++i) //106=sqrt(46340)/2-3if(p[i])for(k=(i<<1)+3,j=(k+1)*(i+1)-1;j<2317

19、0;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;},核心代碼及解釋 （2）,int ttn(int i,int n){ //函數(shù)計算2i mod n=?__int64 t=2,r=1; //用64位長整型防止中間結(jié)果溢出,,while(i) {if(i&1)r=t*

20、r%n;t=t*t%n;i>>=1;}return r;},核心代碼及解釋 （3）,int phi(int n) { // 函數(shù)求phi(n)result=temp=n;k=sqrt(n);for(i=0;prime[i]<=k&&i<nb_prime;++i) if(!(temp%prime[i])) //如果prime[i]是n的因子{do temp/

21、=prime[i];while(!(temp%prime[i]));result=result/prime[i]*(prime[i]-1);k=sqrt(temp);}if(temp-1) //如果n的素數(shù)因子超過46340的范圍result=result/temp*(temp-1); return result;},核心代碼及解釋 （4）,int main(){sieve();whi

22、le(scanf("%d",&n)!=EOF) {if(n1)r[j++]=temp; for(i=0;i<j;++i){ while(x%r[i]==0&&(k=ttn(x,n))==1) x/=r[i]; // result是phi(p)的因子if(k!=1)x*=r[i];} printf(&