C語言程序設(shè)計100例之(10)：最大公約數(shù)

1、C 語言程序設(shè)計100 例之（ 10）：最大公約數(shù)例 10最大公約數(shù)問題描述有三個正整數(shù)a,b,c（ 0a,b,c106 ），其中c 不等于b。若a 和 c 的最大公約數(shù)為b ，現(xiàn)已知a 和 b，求滿足條件的最小的c。輸入數(shù)據(jù)第一行輸入一個n，表示有n 組測試數(shù)據(jù)，接下來的n 行，每行輸入兩個正整數(shù)a,b。輸出格式輸出對應(yīng)的c，每組測試數(shù)據(jù)占一行。輸入樣例26 212 4輸出樣例48（1）編程思路。利用轉(zhuǎn)輾相除法求兩個整數(shù)的最大公約數(shù)。例如，求整數(shù) m=48， n=18 兩個數(shù)的最大公約數(shù)的方法如右圖所示。具體做法是：，若 m%n=0，則 n 是最大公約數(shù)，否則，計算 r=m%n，置 m=n，

2、n=r ，重復(fù)這個過程，直到m%n=0。將求整數(shù) m 和 n 的最大公約數(shù)定義為函數(shù)int gcd(int m,intn) ； 。在本題中，由于b 是 a、 c 的最大公約數(shù)，且c！ =b，所以對 c=2*b 、 3*b 進行窮舉判斷即可直到最小的滿足條件的c。（2）源程序。#include int gcd(int m, int n)int r;while(m%n!=0)r=m%n;m = n;n = r;return n;int main()int t,a,b,c;scanf(%d,&t);while(t-)scanf(%d%d,&a,&b);c=2*b;while(gcd(a,c)!=b)

3、c+=b;printf(%dn,c);return 0;習(xí)題 1010-1Uniform Generator本題選自杭州電子科技大學(xué)OJ 題庫（ http:/ DescriptionComputer simulations often require random numbers. One way to generate pseudo-randomnumbers is via a function of the formseed(x+1) = seed(x) + STEP % MODwhere % is the modulus operator.Such a function will gen

4、erate pseudo-random numbers (seed) between 0 and MOD-1. One problemwith functions of this form is that they will always generate the same pattern over and over. In orderto minimize this effect, selecting the STEP and MOD values carefully can result in a uniformdistribution of all values between (and

5、 including) 0 and MOD-1.For example, if STEP = 3 and MOD = 5, the function will generate the series of pseudo-randomnumbers 0, 3, 1, 4, 2 in a repeating cycle. In this example, all of the numbers between and including0 and MOD-1 will be generated every MOD iterations of the function. Note that by th

6、e nature of thefunction to generate the same seed(x+1) every time seed(x) occurs means that if a function willgenerate all the numbers between 0 and MOD-1, it will generate pseudo-random numbers uniformlywith every MOD iterations.If STEP = 15 and MOD = 20, the function generates the series 0, 15, 10

7、, 5 (or any other repeatingseries if the initial seed is other than 0). This is a poor selection of STEP and MOD because noinitial seed will generate all of the numbers from 0 and MOD-1.Your program will determine if choices of STEP and MOD will generate a uniform distributionof pseudo-random number

8、s.InputEach line of input will contain a pair of integers for STEP and MOD in that order (1 = STEP , MOD= 100000).OutputFor each line of input, your program should print the STEPvalue right- justified in columns 1 through10, the MOD value right-justified in columns 11 through 20 and either Good Choi

9、ce or BadChoice left-justified starting in column 25. The Good Choice message should be printed when theselection of STEP and MOD will generate all the numbers between and including 0 and MOD-1when MOD numbers are generated. Otherwise, your program should print the message BadChoice. After each outp

10、ut test set, your program should print exactly one blank line.Sample Input3 515 2063923 99999Sample Output35Good Choice1520Bad Choice6392399999Good Choice（ 1）編程思路。題目的意思是：輸入兩個整數(shù)x 和 y，若 x 與 y 互質(zhì)，則輸出“ Good Choice”;否則輸出“Bad Choice”。若兩個整數(shù)x 和（ 2）源程序。y 的最大公約數(shù)為1，則 x 與y 互質(zhì)。#include int gcd(int a, int b)int r

11、;while(a%b!=0)r=a%b;a = b;b = r;return b;int main()int x, y;while(scanf(%d %d, &x, &y) != EOF)if(gcd(x, y) = 1)printf(%10d%10dGood Choicenn, x, y);elseprintf(%10d%10dBad Choicenn,x, y);return 0;10-2Party本題選自北大POJ 題庫 （ /problem?id=3970）DescriptionThe CEO of ACM (Association of Cryptograp

12、hic Mavericks) organization has invited all of his teamsto the annual all-hands meeting, being a very disciplined person, the CEO decided to give a moneyaward to the first team that shows up to the meeting.The CEO knows the number of employees in each of his teams and wants to determine X the leasta

13、mount of money he should bring so that he awards the first team to show up such that all teammembers receive the same amount of money. You must write a program to help the CEO achievethis task.InputThe input consists of multiple test cases, each test case is described on a line by itself, Each lines

14、tarts with an integer N (1 = N = 20) the number of teams in the organization followed by Nspace separated positive integers representing the number of employees in each of the N teams.You may assume that X will always fit in a 32 bit signed integer. The last line of input starts with0 and shouldnt b

15、e processed.OutputFor each test case in the input print The CEOmust bring X pounds., where X is as describedabove or Too much money to pay! if X is 1000000 or more.Sample Input1 30000002 12 40Sample OutputToo much money to pay!The CEO must bring 12 pounds.（ 1）編程思路。題意是求輸入的n 個正整數(shù)的最小公倍數(shù)。設(shè)正整數(shù)x 與 y 的最大公約

16、數(shù)為gcd(x,y)，則 x 與 y 的最小公倍數(shù)為x*y/gcd(x,y) 。（ 2）源程序。#include int lcm(int x,int y)int r,a,b;a=x; b=y;while (a%b!=0)r=a%b;a=b;b=r;return x*y/b;int main()int n,i,x0,x1;while(scanf(%d,&n) & n!=0)scanf(%d,&x0);for (i=2;i=1000000)printf(Too much money to pay!n);elseprintf(The CEO must bring %d pounds.n,x0);re

17、turn 0;10-3相遇周期題目描述已知兩顆衛(wèi)星的運行周期，求它們的相遇周期。輸入輸入數(shù)據(jù)的第一行為一個正整數(shù)T，表示測試數(shù)據(jù)的組數(shù)，然后是T 組測試數(shù)據(jù)，每組測試數(shù)據(jù)包含兩組正整數(shù)， 用空格隔開。 每組包含兩個正整數(shù)， 表示轉(zhuǎn) n 圈需要的天數(shù) (26501/6335 ，表示轉(zhuǎn) 26501 圈要 6335 天 )，用 / 隔開。輸出對于每組測試數(shù)據(jù) , 輸出它們的相遇周期，如果相遇周期是整數(shù)則用整數(shù)表示，否則用最簡分?jǐn)?shù)表示。輸入樣例226501/633518468/4229359/1147915725/19170輸出樣例81570078/75431415（ 1）編程思路。輸入的每個分?jǐn)?shù)就是一個衛(wèi)星的周期。求兩個衛(wèi)星的相遇周期，即求二者周期的最小公倍數(shù)。可以先把兩個分?jǐn)?shù)通分，找出通分后兩個分子的最小公倍數(shù)，再除以通分后的分母，即得相遇周期（最小公倍數(shù)）。（ 2）源程序。#include long long gcd(long long m, long long n)long long r;while(m%n!=0)r=m%n;m