基礎(chǔ)數(shù)學(xué)題第1頁(yè)你今天AC了沒(méi)？第2頁(yè)EXAM1058青蛙王子一個(gè)王子被巫師詛咒，變成了一只青蛙。500年后一天，青蛙王子碰到了一個(gè)仙女，仙女告訴他，假如他能經(jīng)過(guò)一個(gè)簡(jiǎn)單測(cè)試，她就能幫他解除詛咒。測(cè)試是這么子，仙女要青蛙王子在一條直線上跳躍（青蛙王子最開(kāi)始站在坐標(biāo)為0地方），但只能按照她給定兩種長(zhǎng)度跳躍（假設(shè)這兩種長(zhǎng)度王子都能跳到），能夠往前或者往后跳，假如能到達(dá)指定地點(diǎn)，那么就經(jīng)過(guò)測(cè)試；仙女給定方式有各種，但有些是不可能滿足到達(dá)指定地點(diǎn)。請(qǐng)你幫幫可憐青蛙王子，尋找出那些能夠完成測(cè)試跳躍方式。第3頁(yè)？第4頁(yè)題目很簡(jiǎn)單，其實(shí)就是求兩個(gè)數(shù)最大條約數(shù)gcd(a,b)gcd一些性質(zhì)假如a=b則gcd(a,b)=a假如a,b是偶數(shù)則gcd(a,b)=2*gcd(a/2,b/2)假如a為偶數(shù)，b為奇數(shù)，則gcd(a,b)=gcd(a/2,b）假如a和b均為奇數(shù)，則gcd(a,b)=gcd(a-b,b)gcd(a,b)=gcd(b,b%a)第5頁(yè)歐幾里德算法（輾轉(zhuǎn)相除法）intgcd(intm,intn)//Euclid{ intr=(m%n+n)%n; while(r) {m=n;n=r;r=m%n;} returnn;}第6頁(yè)佳佳迷惑給出一個(gè)數(shù)，含數(shù)字1,2,3,4,把N全部數(shù)字重新排列一下組成一個(gè)新數(shù)，使得它是7倍數(shù)第7頁(yè)余數(shù)0123456排列3241132412342341124313422134把數(shù)字1，2，3，4抽出來(lái)，其它數(shù)字組成數(shù)w，則w*10000整除7余數(shù)有7種可能。得到這7種組合以后，只要用1，2，3，4配出對(duì)應(yīng)組合就可得到解。第8頁(yè)整除和約數(shù)a,b是整數(shù)，a!=0,存在整數(shù)c，使得b=ac,則a|b,a是b一個(gè)因子，b是a倍數(shù)。性質(zhì)若a|b,a|c，則a|(b+c)若a|b,那么對(duì)全部整數(shù)c,a|bc若a|b,b|c,則a|c.第9頁(yè)同余a為整數(shù)，d為正整數(shù),那么有唯一整數(shù)q和r，其中0<=r<d,使得a=dq+r。假如a,b除以c得到余數(shù)相等，則稱a,b同余,記做a≡b(modc)a≡a1,b≡b1(modc),則a+b≡a1+b1(modc)a-b≡a1-b1(modc)a*b≡a1*b1(modc)假如ac≡bd,c≡d(modm)，且gcd(c,m)=1，則a≡b(modm)第10頁(yè)素?cái)?shù)p是整數(shù)，p>1,假如p只含因子1和p，則p是素?cái)?shù)尋找素?cái)?shù)找出1——n之間全部素?cái)?shù)給定一個(gè)數(shù)，它是不是素?cái)?shù)第11頁(yè)判斷n是不是素?cái)?shù)樸素判斷法試除從2開(kāi)始全部小于n自然數(shù)。O(n)假如a是n因子，那么n/a必定也是n因子，所以假如n有一個(gè)大于1真因子，那么必有一個(gè)小于n0.5因子。O(n0.5)假如n是合數(shù)，那么必有一個(gè)素因子小于n0.5,假如要檢測(cè)M是否為素?cái)?shù)，能夠事先建立一個(gè)M0.5之內(nèi)素?cái)?shù)表，假設(shè)其大小為k。O(k)第12頁(yè)intisPrime(intx) { inti,k=(int)sqrt((double)x); for(i=2;i<=k;i++) if(x%i==0)return0; return1; }第13頁(yè)找出1——n之間全部素?cái)?shù)？把1到n之間數(shù)全部測(cè)試一遍 假如n很大了？？太慢?。。?！篩法 每次求出一個(gè)素?cái)?shù)p，就將n之內(nèi)它全部倍數(shù)都篩掉。實(shí)現(xiàn)時(shí)，對(duì)于一個(gè)素?cái)?shù)p，只需要篩去p*p,p*(p+1)，…,等就能夠了。第14頁(yè)#include<stdio.h>#defineN1000000boolb[N+1]={1,1,0};//標(biāo)志數(shù)組intp[N];//存素?cái)?shù)intmain(){inti,j,k;intn=0;

for(i=4;i<=N;i+=2)b[i]=1;k=3;while(k*k<=N){for(i=k*k;i<=N;i+=2*k)b[i]=1;while(b[++k]);}for(i=2;i<=N;i++)if(b[i]==0)p[n++]=i;

//結(jié)果放在p里，輸出前一百個(gè)for(i=0;i<100;i++) printf("%d",p[i]);return0;}第15頁(yè)外星人計(jì)數(shù)年省賽可能是因?yàn)橛?0個(gè)手指原因，所以我們把0～9十個(gè)數(shù)字組合起來(lái)表示任意數(shù)值，但這并不是唯一可能記數(shù)法。在某個(gè)外星球居住著一個(gè)智慧生物，他們手跟我們手結(jié)構(gòu)不一樣，他們記數(shù)法也很奇特。他們用三個(gè)記號(hào)’0’,’1’,’-’組合來(lái)表示數(shù)值，這三個(gè)記號(hào)分別對(duì)應(yīng)數(shù)值0,1,-1。在他們數(shù)值系統(tǒng)中，每個(gè)數(shù)位是右邊相鄰數(shù)位3倍。所以數(shù)’10-’表示數(shù)值8（因?yàn)?＝1×9＋0×3＋－1×1），數(shù)’-1’表示數(shù)值-2（因?yàn)?2=-1×3＋1×1）。編寫(xiě)程序，讀入一組-231至231－1之間數(shù)值，輸出對(duì)應(yīng)外星球數(shù)值表示。第16頁(yè)？第17頁(yè)這是一道進(jìn)制轉(zhuǎn)換題平衡三進(jìn)制-1，0，1第18頁(yè)任意進(jìn)制轉(zhuǎn)10進(jìn)制計(jì)算權(quán)值，累加即可10進(jìn)制轉(zhuǎn)任意進(jìn)制不停用進(jìn)制數(shù)去除被除數(shù)，直到被除數(shù)為0停頓，余數(shù)序列即為所求11轉(zhuǎn)成2進(jìn)制數(shù)111512011011=(1011)2第19頁(yè)任意進(jìn)制轉(zhuǎn)換第20頁(yè)0，1，2，3，4，5，6，7，8，9，10，11，12，130，1，1-，10，11，1--，1-0，1-1，10-，100，101，11-，111第21頁(yè)計(jì)算ab%c值利用(a*a)%c=((a%c)*(a%c))%c當(dāng)b很大時(shí)，速度很慢利用二進(jìn)制掃描法，將b化成2進(jìn)制(atat-1...a0)2，第22頁(yè)intintCal(intinta,intintn,intintk){if(!a)//假如a==0值為0return0;

intr=1;//當(dāng)前余數(shù)rwhile(n--){if(n&1)//假如n是奇數(shù)r=r*a%k;else{n>>=1;//a^n=a^2^sqrt(n)a*=a;a%=k;}}returnr;}第23頁(yè)P(yáng)OJ1061青蛙約會(huì)兩只青蛙在網(wǎng)上相識(shí)了，它們聊得很開(kāi)心，于是以為很有必要見(jiàn)一面。它們很高興地發(fā)覺(jué)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止?？墒撬鼈兂霭l(fā)之前忘記了一件很主要事情，既沒(méi)有問(wèn)清楚對(duì)方特征，也沒(méi)有約定見(jiàn)面詳細(xì)位置。不過(guò)青蛙們都是很樂(lè)觀，它們以為只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方。不過(guò)除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面。為了幫助這兩只樂(lè)觀青蛙，你被要求寫(xiě)一個(gè)程序來(lái)判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。

我們把這兩只青蛙分別叫做青蛙A和青蛙B，而且要求緯度線上東經(jīng)0度處為原點(diǎn)，由東往西為正方向，單位長(zhǎng)度1米，這么我們就得到了一條首尾相接數(shù)軸。設(shè)青蛙A出發(fā)點(diǎn)坐標(biāo)是x，青蛙B出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費(fèi)時(shí)間相同。緯度線總長(zhǎng)L米?，F(xiàn)在要你求出它們跳了幾次以后才會(huì)碰面。第24頁(yè)P(yáng)OJ1061輸入只包含一行5個(gè)整數(shù)x，y，m，n，L，其中x≠y<000000，0<m、n<000000，0<L<2100000000。輸出碰面所需要跳躍次數(shù)，假如永遠(yuǎn)不可能碰面則輸出一行"Impossible"第25頁(yè)思緒兩只青蛙跳了t步A坐標(biāo)x+mtB坐標(biāo)y+nt相遇充要條件：

x+mt-y-nt=pL(pZ)即

(n-m)*t+Lp=x-y(L>0)第26頁(yè)問(wèn)題轉(zhuǎn)化為：求滿足A*t+Lp=B最小t(t>0)即求一次同余方程A*t=B(modL)最小正整數(shù)解

第27頁(yè)至此，我們已經(jīng)將問(wèn)題完全轉(zhuǎn)化成一個(gè)數(shù)學(xué)問(wèn)題了，但問(wèn)題是…….第28頁(yè)HowtoSolveit?第29頁(yè)算法一：窮舉A*t=B(modL)注意到：上面方程解是模L同余所以能夠試一下窮舉

搜索被稱為“通用解題法”，在算法中占有主要地位搜索算法也是有不少技術(shù)含量代碼（略）第30頁(yè)顯然上面算法是會(huì)超時(shí)第31頁(yè)算法二解ax=b(modn)方程

等價(jià)于存在y，使得ax-ny=b。記d=gcd(a,n),a=d*a`,n=d*n`,那么必有d|b。求解a`x-n`y=b/d。x不是唯一，但x全部解相差n`整數(shù)倍x,x+n/d,x+2*n/d+…+x+(d-1)*n/d第32頁(yè)擴(kuò)展歐幾里德算法假如gcd（a,b）=d,那么一定存在x,y滿足ax+by=d。intgcd(intp,intq,int*x,int*y){ intx1,y1;/*previouscoefficients*/ intg;/*valueofgcd(p,q)*/ if(q>p)return(gcd(q,p,y,x)); if(q==0){ *x=1; *y=0; return(p); } g=gcd(q,p%q,&x1,&y1); *x=y1; *y=(x1-floor(p/q)*y1); return(g);}第33頁(yè)typedefunsignedintintint64//g++int64exgcd(int64m,int64&x,int64n,int64&y)//ExtendEuclid{ int64x1,y1,x0,y0; x0=1;y0=0; x1=0;y1=1;int64r=(m%n+n)%n; int64q=(m-r)/n; x=0;y=1; while(r) {x=x0-q*x1;y=y0-q*y1;x0=x1;y0=y1; x1=x;y1=y; m=n;n=r;r=m%n; q=(m-r)/n; } returnn;}第34頁(yè)intmain(){ int64r,t; int64x,y,m,n,l; cin>>x>>y>>m>>n>>l; int64ar,br; int64M=exgcd(n-m,ar,l,br); if((x-y)%M||m==n) cout<<"Impossible"<<endl; else {