基础数学题省公开课一等奖全国示范课微课金奖

基础数学题第1页你今天AC了没？第2页EXAM1058青蛙王子一个王子被巫师诅咒，变成了一只青蛙。500年后一天，青蛙王子碰到了一个仙女，仙女告诉他，假如他能经过一个简单测试，她就能帮他解除诅咒。测试是这么子，仙女要青蛙王子在一条直线上跳跃（青蛙王子最开始站在坐标为0地方），但只能按照她给定两种长度跳跃（假设这两种长度王子都能跳到），能够往前或者往后跳，假如能到达指定地点，那么就经过测试；仙女给定方式有各种，但有些是不可能满足到达指定地点。请你帮帮可怜青蛙王子，寻找出那些能够完成测试跳跃方式。第3页？第4页题目很简单，其实就是求两个数最大条约数gcd(a,b)gcd一些性质假如a=b则gcd(a,b)=a假如a,b是偶数则gcd(a,b)=2*gcd(a/2,b/2)假如a为偶数，b为奇数，则gcd(a,b)=gcd(a/2,b）假如a和b均为奇数，则gcd(a,b)=gcd(a-b,b)gcd(a,b)=gcd(b,b%a)第5页欧几里德算法（辗转相除法）intgcd(intm,intn)//Euclid{ intr=(m%n+n)%n; while(r) {m=n;n=r;r=m%n;} returnn;}第6页佳佳迷惑给出一个数，含数字1,2,3,4,把N全部数字重新排列一下组成一个新数，使得它是7倍数第7页余数0123456排列3241132412342341124313422134把数字1，2，3，4抽出来，其它数字组成数w，则w*10000整除7余数有7种可能。得到这7种组合以后，只要用1，2，3，4配出对应组合就可得到解。第8页整除和约数a,b是整数，a!=0,存在整数c，使得b=ac,则a|b,a是b一个因子，b是a倍数。性质若a|b,a|c，则a|(b+c)若a|b,那么对全部整数c,a|bc若a|b,b|c,则a|c.第9页同余a为整数，d为正整数,那么有唯一整数q和r，其中0<=r<d,使得a=dq+r。假如a,b除以c得到余数相等，则称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页素数p是整数，p>1,假如p只含因子1和p，则p是素数寻找素数找出1——n之间全部素数给定一个数，它是不是素数第11页判断n是不是素数朴素判断法试除从2开始全部小于n自然数。O(n)假如a是n因子，那么n/a必定也是n因子，所以假如n有一个大于1真因子，那么必有一个小于n0.5因子。O(n0.5)假如n是合数，那么必有一个素因子小于n0.5,假如要检测M是否为素数，能够事先建立一个M0.5之内素数表，假设其大小为k。O(k)第12页intisPrime(intx) { inti,k=(int)sqrt((double)x); for(i=2;i<=k;i++) if(x%i==0)return0; return1; }第13页找出1——n之间全部素数？把1到n之间数全部测试一遍 假如n很大了？？太慢！！！！筛法 每次求出一个素数p，就将n之内它全部倍数都筛掉。实现时，对于一个素数p，只需要筛去p*p,p*(p+1)，…,等就能够了。第14页#include<stdio.h>#defineN1000000boolb[N+1]={1,1,0};//标志数组intp[N];//存素数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;

//结果放在p里，输出前一百个for(i=0;i<100;i++) printf("%d",p[i]);return0;}第15页外星人计数年省赛可能是因为有10个手指原因，所以我们把0～9十个数字组合起来表示任意数值，但这并不是唯一可能记数法。在某个外星球居住着一个智慧生物，他们手跟我们手结构不一样，他们记数法也很奇特。他们用三个记号’0’,’1’,’-’组合来表示数值，这三个记号分别对应数值0,1,-1。在他们数值系统中，每个数位是右边相邻数位3倍。所以数’10-’表示数值8（因为8＝1×9＋0×3＋－1×1），数’-1’表示数值-2（因为-2=-1×3＋1×1）。编写程序，读入一组-231至231－1之间数值，输出对应外星球数值表示。第16页？第17页这是一道进制转换题平衡三进制-1，0，1第18页任意进制转10进制计算权值，累加即可10进制转任意进制不停用进制数去除被除数，直到被除数为0停顿，余数序列即为所求11转成2进制数111512011011=(1011)2第19页任意进制转换第20页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页计算ab%c值利用(a*a)%c=((a%c)*(a%c))%c当b很大时，速度很慢利用二进制扫描法，将b化成2进制(atat-1...a0)2，第22页intintCal(intinta,intintn,intintk){if(!a)//假如a==0值为0return0;

intr=1;//当前余数rwhile(n--){if(n&1)//假如n是奇数r=r*a%k;else{n>>=1;//a^n=a^2^sqrt(n)a*=a;a%=k;}}returnr;}第23页POJ1061青蛙约会两只青蛙在网上相识了，它们聊得很开心，于是以为很有必要见一面。它们很高兴地发觉它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很主要事情，既没有问清楚对方特征，也没有约定见面详细位置。不过青蛙们都是很乐观，它们以为只要一直朝着某个方向跳下去，总能碰到对方。不过除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面。为了帮助这两只乐观青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B，而且要求纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这么我们就得到了一条首尾相接数轴。设青蛙A出发点坐标是x，青蛙B出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。第24页POJ1061输入只包含一行5个整数x，y，m，n，L，其中x≠y<000000，0<m、n<000000，0<L<2100000000。输出碰面所需要跳跃次数，假如永远不可能碰面则输出一行"Impossible"第25页思绪两只青蛙跳了t步A坐标x+mtB坐标y+nt相遇充要条件：

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

(n-m)*t+Lp=x-y(L>0)第26页问题转化为：求满足A*t+Lp=B最小t(t>0)即求一次同余方程A*t=B(modL)最小正整数解

第27页至此，我们已经将问题完全转化成一个数学问题了，但问题是…….第28页HowtoSolveit?第29页算法一：穷举A*t=B(modL)注意到：上面方程解是模L同余所以能够试一下穷举

搜索被称为“通用解题法”，在算法中占有主要地位搜索算法也是有不少技术含量代码（略）第30页显然上面算法是会超时第31页算法二解ax=b(modn)方程

等价于存在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`整数倍x,x+n/d,x+2*n/d+…+x+(d-1)*n/d第32页扩展欧几里德算法假如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页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页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 {