入门数论a程序设计基础

ACM程序设计基础----简单数学题2023/1/102HDOJ_1108

最小公倍数给定两个正整数，计算这两个数的最小公倍数。1014702023/1/103欧几里德算法intgcd(intda,intxiao){inttemp;while(xiao!=0){temp=da%xiao;da=xiao;xiao=temp;}return(da);}思考：递归的形式如何写？2023/1/104HDOJ_1061

RightmostDigitGivenapositiveintegerN,youshouldoutputthemostrightdigitofN^N(1<=N<=1,000,000,000).34762023/1/105HDOJ_1061

RightmostDigit数据规模很大暴力方法该打基本思路规律2023/1/106规律0，1还有？5，64还有？92，3，7，8？6,2,4,8…………2023/1/107#include<stdio.h>

intmain(void)

{

longn;

inta[10][4]={{0},{1},{6,2,4,8},{1,3,9,7},{6,4},{5},{6},{1,7,9,3},{6,8,4,2},{1,9}},d,num;

scanf("%d",&num);

2023/1/108while(num--)

{

scanf("%ld",&n);

d=n%10;

if(d==0||d==1||d==5||d==6)

printf("%d\n",d);

elseif(d==4||d==9)

printf("%d\n",a[d][n%2]);

elseif(d==2||d==3||d==7||d==8)

printf("%d\n",a[d][n%4]);

}

return0;

}2023/1/109HDOJ_2035人见人爱A^B求A^B的最后三位数表示的整数（1<=A,B<=10000）2312689842023/1/1010HDOJ_2035人见人爱A^B最暴力的暴力？改进的暴力？二分加速？2023/1/1011#include<iostream>

usingnamespacestd;

intmain()

{

inta,b,i,mul;

while(cin>>a>>b)

{

if(a==0&&b==0)

break;

mul=a%1000;

for(i=1;i<b;i++)

{

mul=mul*(a%1000);

mul=mul%1000;

}

cout<<mul<<endl;

}

return0;

}2023/1/1012HDOJ_1425

sort给你n个整数，请按从大到小的顺序输出其中前m大的数。每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。533-3592213-6442139232023/1/1013HDOJ_1425

sort常规的思想是？常规的结果是？数据的特点是？加速的方法是？思考：如果数据可以重复呢？2023/1/1014#include<stdio.h>

#include<string.h>

inthash[1000001];

intmain()

{

intn;

intm;

inti;

inttemp;

while(scanf("%d%d",&n,&m)!=EOF)

{

memset(hash,0,sizeof(hash));

for(i=0;i<n;i++)

{

scanf("%d",&temp);

hash[temp]=1;

}

intcount=0;

for(i=1000000;i>=0;i--)

{

if(hash[i])

{

printf("%d",i-500000);

count++;

}

if(count==m)

break;

}

printf("\n");}

return0;

}空间换时间2023/1/10151021FibonacciAgain2023/1/1016题目分析：能被3整除的整数的特点？还要看程序吗？如果两个数的和能被3整除，这两个数有什么特点？关于“和”能否被3整除，这两个数一共有多少种组合？如果F（x）和F（y）相等的话，会出现什么重要信息？2023/1/1017Hdoj_1021程序清单：#include<stdio.h>intmain(){longn;while(scanf("%ld",&n)!=EOF) if(n%8==2||n%8==6) printf("yes\n"); else printf("no\n"); return0;}2023/1/1018ProblemB:NumberSequence2023/1/1019题目特点： 这个题目是一个比较典型的ACM竞赛题，尽管在真正的大赛中这个题目可能算比较简单的，但在校赛中，本题难度属于中等，可以说，能做出本题的队伍基本都有银奖以上。 但如果不认真分析，有可能会掉入陷阱。2023/1/1020题意：已知：f(1)=1,f(2)=1,f(n)=(A*f(n–1)+B*f(n–2))mod7，给出A、B、n，求f(n)。2023/1/1021题目分析： 对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。

暴力（Brute-Force）能解决问题吗？2023/1/1022现在对这题有什么想法???2023/1/1023思路：Mod7？f(n)值仅有0到6这七种取值。由于“f(n)=A*f(n–1)+B*f(n–2)”并且只有7种取值。所以f(1)到f(无穷大)构成了一个循环数组。又：f(n-1)与f(n-2)的值组合的不同情况只有7*7=49种，可以在可观的时间内求出循环部分的序列。只要求出循环周期即可求出f(n)的特征序列。然后用f(n%t)快速求出f(n)的值。2023/1/1024#include<stdio.h>

intmain()

{

inta,b,i;

longn,f[201];

while(scanf(“%d%d%ld”,&a,&b,&n)!=EOF)

{

if(a==0&&b==0&&n==0)break;

f[1]=1;

f[2]=1;

if(n>=3)

{

for(i=3;i<200;i++)

{f[i]=(a*f[i-1]+b*f[i-2])%7;if(f[i-1]==1&&f[i]==1)

break;

}

2023/1/1025printf(“%ldn”,f[n]);

}

else

printf(“1n”);

}

return0;

}i=i-2;

n=n%i;

if(n==0)

n=i;

2023/1/1026一般顺序查找表的查找算法简单，但查找效率比较低，特别不适用于表长较大的查找表。二分查找若以查找表数据是有序的，则查找过程可以基于“折半”进行。2023/1/1027二分法算法需要设三个指示器low、high、mid，分别指向查找范围的开始、最后和中间位置。假定有15个元素，则一开始low=1、high=15、mid=(low+high)/2。这时high一定大于low。接着进行以下判断：如x=a[mid]则设查到标志为‘真’，打印有关信息。如x<a[mid]则下一步查找范围应该在low到mid-1之间，改变high使之等于mid-1。如x>a[mid]则下一步查找范围应该在mid+1到high之间，改变low使之等于mid+1。重复以上过程直到low>high或已经找到为止。2023/1/1028ST.elemST.length例如:key=64的查找过程如下lowhighmidlow

mid

high

midlow指示查找区间的下界;high指示查找区间的上界;mid=(low+high)/2。2023/1/1029#defineN15main(){inta[N];intlow,high,mid,x,j,find;for(j=0;j<N;j++)scanf("%d",&a[j]);printf("inputxtofind:\n");scanf("%d",&x);low=0;high=N-1;find=0;

二分法实现2023/1/1030do{mid=(low+high)/2;if(x==a[mid]){printf("Find:%3din%3d",x,mid+1);find=1;}elseif(x<a[mid])high=mid-1;elseif(x>a[mid])low=mid+1;}while((high>=low)&&!find);if(!find)printf("%3dnotbeenfound.",x);}二分法实现2023/1/1031先看一个具体的情况，假设：n=11分析折半