首页 > 分享 > ZUST 程序设计算法竞赛基础【1】题解报告

ZUST 程序设计算法竞赛基础【1】题解报告

花匠小妙招
2024-09-16 23:04

3.6 题解报告 1001 最小公倍数题目题解代码 1002 人见人爱A^B 题目题解代码 1003 Rightmost Digit 题目题解代码 1004 Climbing Worm 题目题解代码 1005 Balloon Comes! 题目题解代码 1006 Fibonacci Again 题目题解代码 1007 Number Sequence 题目题解代码 1008 sort 题目题解代码 1009 吃糖果题目题解代码 1010 Sum Problem 题目题解代码 1011 Elevator 题目题解代码 1012 七夕节题目题解代码

1001 最小公倍数

题目

Problem Description

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

Input

输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.

Output

对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。

Sample Input

10 14

Sample Output

70

题解

求最小公倍数算法：

最小公倍数=两整数的乘积÷最大公约数 1

求最大公约数算法：

1.辗转相除法有两整数a和b： ① a%b得余数c ② 若c=0，则b即为两数的最大公约数 ③ 若c≠0，则a=b，b=c，再回去执行① 2.相减法有两整数a和b： ① 若a>b，则a=a-b ② 若a<b，则b=b-a ③ 若a=b，则a（或b）即为两数的最大公约数 ④ 若a≠b，则再回去执行① 3.穷举法有两整数a和b： ① i=1 ② 若a，b能同时被i整除，则t＝i ③ i++ ④ 若 i <= a(或b)，则再回去执行② ⑤ 若 i > a(或b)，则t即为最大公约数，结束改进： ① i= a(或b) ② 若a，b能同时被i整除，则i即为最大公约数，结束 ③ i--，再回去执行② 有两整数a和b： ① i=1 ② 若a，b能同时被i整除，则t＝i ③ i++ ④ 若 i <= a(或b)，则再回去执行② ⑤ 若 i > a(或b)，则t即为最大公约数，结束改进： ① i= a(或b) ② 若a，b能同时被i整除，则i即为最大公约数，结束 ③ i--，再回去执行② --------------------- 作者：iwm_next 来源：CSDN 原文：https://blog.csdn.net/iwm_next/article/details/7450424

1234567891011121314151617181920212223242526272829303132333435363738394041424344

代码

#include<stdio.h> int main() { int n1,n2,i,j,temp=0; while(scanf("%d %d",&n1,&n2)!=EOF) {i=n1>n2?n1:n2;j=n1<n2?n1:n2; do{ temp=j; j=i%j;i=temp; } while(j!=0); printf("%dn",n1/i*n2); } return 0; }

123456789101112131415161718

1002 人见人爱A^B

题目

Problem Description

求A^B的最后三位数表示的整数。

说明：A^B的含义是“A的B次方”

Input

输入数据含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000）
如果A=0, B=0，则表示输入数据的结束，不做处理。

Output

对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

Sample Input

2 3
12 6
6789 10000
0 0

Sample Output

8
984
1

题解

由于只需要输出最后三位，就不需要考虑前面，直接取乘数A的最后三位相乘，再取积的最后三位继续进行计算，就可以比较快捷。
注意：A的位数

代码

#include<stdio.h> int main(){int a,b,i,sum=1;while(scanf("%d %d",&a,&b)!=EOF){sum=1;if(a!=0&&b!=0){a=a%100;for(i=0;i<b;i++)sum=a*sum%1000;printf("%dn",sum);}}return 0;} 1234567891011121314

1003 Rightmost Digit

题目

Problem Description

Given a positive integer N, you should output the most right digit of N^N.

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.Each test case contains a single positive integer N(1<=N<=1,000,000,000).

Output

For each test case, you should output the rightmost digit of N^N.

Sample Input

2
3
4

Sample Output

7
6

Hint

In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.
In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.