算法02简单数学题

ACM程序设计2023/10/62第二讲基础数学题2023/10/63引言在ACM竞赛中,经常可以看到数学问题的身影可以是纯数学问题,也可以是需要利用数学上的一些公式,定理,算法来辅助解决的问题会者不难,而不会的选手在赛场上一般很难推出公式或进行证明往往想起来费劲,写起来却很轻松2023/10/64“依然”从简单题说起：SUM(n)=1+2+3+...+nYoumayassumetheresultwillbeintherangeof32-bitsignedinteger.Sampleinput:10Sampleoutput:55

2023/10/65很常见的一种写法：#include<stdio.h>intmain(){intn,i,sum=0;

scanf("%d",&n);for(i=1;i<=n;i++)sum=sum+i;printf("%d\n",sum);return0;}2023/10/66HDOJ_1008:Elevator2023/10/67

这是2004浙江省赛最简单的一题，当时训练水平相对较高的学校基本上10分钟之内解决该题，这是一个没有算法的简单模拟题目。入门训练的好选择～题目评述：2023/10/68同余相关整除的性质欧几里德算法2023/10/69整除的性质性质1a|b,b|c=>a|c性质2a|b=>a|bc性质3a|b,a|c=>a|kb±lc性质4a|b,b|a=>a=±b性质5a=kb±c=>a,b的公因数与b,c的公因数完全相同2023/10/610整除的性质性质5a=kb±c=>a,b的公因数与b,c的公因数完全相同利用性质3(a|b,a|c=>a|kb±lc)证明:对于任意的a,b的公因数da=kb±c=>c=±(a-kb)=>d|c2023/10/611最大公约数最小公倍数求最大公约数:欧几里德算法(辗转相除法,短除法)原理:若a≡r(modb),则gcd(a,b)=gcd(b,r)可利用性质5(a=kb±c=>a,b的公因数与b,c的公因数完全相同)证明最小公倍数:lcm(a,b)=a*b/gcd(a,b)2023/10/612GCD求解过程1014x10104x104x24xx=22023/10/613欧几里德算法欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项)空间复杂度:O(1)但是,对于大整数来说,取模运算非常耗时2023/10/614HDOJ_1108

最小公倍数

给定两个正整数，计算这两个数的最小公倍数。

Input：

1014Output：

70思考：如何求最小公倍数(LCM)？LCM=>GCD2023/10/615欧几里德算法intgcd(intda,intxiao){inttemp;while(xiao!=0){temp=da%xiao;da=xiao;xiao=temp;}return(da);}思考：递归的形式如何写？2023/10/616Stein算法另一种算法:Stein算法渐近时间,空间复杂度均与欧几里德算法相同原理:gcd(ka,kb)=k*gcd(a,b)最大特点:只有移位和加减法计算,避免了大整数的取模运算2023/10/617Stein算法2023/10/618HDOJ_1061

RightmostDigit

GivenapositiveintegerN,youshouldoutputthemostrightdigitofN^N(1<=N<=1,000,000,000).34762023/10/619HDOJ_1061

RightmostDigit对于数字0~9,它们的N次方,我们只看最后一个数字:

0^1=0;0^2=0;循环周期T=1;

1^1=1;1^2=1;循环周期T=1;

2^1=2;2^2=4;2^3=8;2^4=62^5=2;循环周期T=4;

3^1=3;3^2=9;3^3=7;3^4=1;3^5=3;循环周期T=4;

4^1=4;4^2=6;4^3=4;循环周期T=2;后面的大家可以自己算,会得出一个规律:

他们的循环周期只有1,2,4这三种,所以对于源代码里的b,我们可以只算b%4次就可以了,大大减少了循环的次数。至于b%4后面+4,就是为了省下ifelse结构要不就会变成下面这样,不过也都差不多2023/10/620解决方案：#include<iostream>

usingnamespacestd;

intmain()

{

inta,b,n,t,result;

cin>>n;

while(n--)

{

cin>>t;

a=t%10;

b=t%4;

if(b==0)cout<<a*a*a*a%10<<endl;

else

{