例10 最大公約數 問題描述 有三個正整數a,b,c（0<a,b,c<10^6），其中c不等於b。若a和c的最大公約數為b，現已知a和b，求滿足條件的最小的c。 輸入數據 第一行輸入一個n，表示有n組測試數據，接下來的n行，每行輸入兩個正整數a,b。 輸出格式 輸出對應的c，每組測試數據占一行。 輸 ...
例10 最大公約數
問題描述
有三個正整數a,b,c（0<a,b,c<10^6），其中c不等於b。若a和c的最大公約數為b，現已知a和b，求滿足條件的最小的c。
輸入數據
第一行輸入一個n，表示有n組測試數據，接下來的n行，每行輸入兩個正整數a,b。
輸出格式
輸出對應的c，每組測試數據占一行。
輸入樣例
2
6 2
12 4
輸出樣例
4
8
（1）編程思路。
利用轉輾相除法求兩個整數的最大公約數。例如，求整數m=48，n=18兩個數的最大公約數的方法如左圖所示。
具體做法是：，若m%n==0，則n是最大公約數，否則，計算 r=m%n，置m=n，n=r，重覆這個過程，直到m%n==0。
將求整數m和n的最大公約數定義為函數
int gcd(int m,intn)； 。
在本題中，由於b是a、c的最大公約數，且c！=b，所以對c=2*b、3*b…進行窮舉判斷即可直到最小的滿足條件的c。
（2）源程式。
#include <stdio.h>
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)
c+=b;
printf("%d\n",c);
}
return 0;
}
習題10
10-1 Uniform Generator
本題選自杭州電子科技大學OJ題庫 （http://acm.hdu.edu.cn/showproblem.php?pid=1014）
Problem Description
Computer simulations often require random numbers. One way to generate pseudo-random numbers is via a function of the form
seed(x+1) = [seed(x) + STEP] % MOD
where '%' is the modulus operator.
Such a function will generate pseudo-random numbers (seed) between 0 and MOD-1. One problem with functions of this form is that they will always generate the same pattern over and over. In order to minimize this effect, selecting the STEP and MOD values carefully can result in a uniform distribution of all values between (and including) 0 and MOD-1.
For example, if STEP = 3 and MOD = 5, the function will generate the series of pseudo-random numbers 0, 3, 1, 4, 2 in a repeating cycle. In this example, all of the numbers between and including 0 and MOD-1 will be generated every MOD iterations of the function. Note that by the nature of the function to generate the same seed(x+1) every time seed(x) occurs means that if a function will generate all the numbers between 0 and MOD-1, it will generate pseudo-random numbers uniformly with every MOD iterations.
If STEP = 15 and MOD = 20, the function generates the series 0, 15, 10, 5 (or any other repeating series if the initial seed is other than 0). This is a poor selection of STEP and MOD because no initial 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 distribution of pseudo-random numbers.
Input
Each line of input will contain a pair of integers for STEP and MOD in that order (1 <= STEP, MOD <= 100000).
Output
For each line of input, your program should print the STEP value right- justified in columns 1 through 10, the MOD value right-justified in columns 11 through 20 and either "Good Choice" or "Bad Choice" left-justified starting in column 25. The "Good Choice" message should be printed when the selection of STEP and MOD will generate all the numbers between and including 0 and MOD-1 when MOD numbers are generated. Otherwise, your program should print the message "Bad Choice". After each output test set, your program should print exactly one blank line.
Sample Input
3 5
15 20
63923 99999
Sample Output
3 5 Good Choice
15 20 Bad Choice
63923 99999 Good Choice
（1）編程思路。
題目的意思是：輸入兩個整數x和y，若x與y互質，則輸出“Good Choice”;否則輸出“Bad Choice”。
若兩個整數x和y的最大公約數為1，則x與y互質。
（2）源程式。
#include <stdio.h>
int gcd(int a, int b)
{
int r;
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%10d Good Choice\n\n", x, y);
else
printf("%10d%10d Bad Choice\n\n",x, y);
}
return 0;
}
10-2 Party
本題選自北大POJ題庫 （http://poj.org/problem?id=3970）
Description
The CEO of ACM (Association of Cryptographic Mavericks) organization has invited all of his teams to the annual all-hands meeting, being a very disciplined person, the CEO decided to give a money award 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 least amount of money he should bring so that he awards the first team to show up such that all team members receive the same amount of money. You must write a program to help the CEO achieve this task.
Input
The input consists of multiple test cases, each test case is described on a line by itself, Each line starts with an integer N (1 <= N <= 20) the number of teams in the organization followed by N space 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 with 0 and shouldn't be processed.
Output
For each test case in the input print "The CEO must bring X pounds.", where X is as described above or "Too much money to pay!" if X is 1000000 or more.
Sample Input
1 3000000
2 12 4
0
Sample Output
Too much money to pay!
The CEO must bring 12 pounds.
（1）編程思路。
題意是求輸入的n個正整數的最小公倍數。設正整數x與y的最大公約數為gcd(x,y)，則x與y的最小公倍數為x*y/gcd(x,y)。
（2）源程式。
#include <stdio.h>
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<=n;i++)
{
scanf("%d",&x1);
x0=lcm(x0,x1);
}
if (x0>=1000000)
printf("Too much money to pay!\n");
else
printf("The CEO must bring %d pounds.\n",x0);
}
return 0;
}
10-3 相遇周期
題目描述
已知兩顆衛星的運行周期，求它們的相遇周期。
輸入
輸入數據的第一行為一個正整數T，表示測試數據的組數，然後是T組測試數據，每組測試數據包含兩組正整數，用空格隔開。每組包含兩個正整數，表示轉n圈需要的天數(26501/6335，表示轉26501圈要6335天)，用'/'隔開。
輸出
對於每組測試數據, 輸出它們的相遇周期，如果相遇周期是整數則用整數表示，否則用最簡分數表示。
輸入樣例
2
26501/6335 18468/42
29359/11479 15725/19170
輸出樣例
81570078/7
5431415
（1）編程思路。
輸入的每個分數就是一個衛星的周期。求兩個衛星的相遇周期，即求二者周期的最小公倍數。可以先把兩個分數通分，找出通分後兩個分子的最小公倍數，再除以通分後的分母，即得相遇周期（最小公倍數）。
（2）源程式。
#include <stdio.h>
long long gcd(long long m, long long n)
{
long long r;
while(m%n!=0)
{
r=m%n;
m = n;
n = r;
}
return n;
}
int main()
{
int t;
long long a,b,c,d,e,f,n,m,k;
scanf("%d",&t);
while(t--)
{
scanf("%lld/%lld%lld/%lld",&a,&b,&c,&d);
e=b*c;
f=a*d;
m=b*d; //通分
n=gcd(f,e);
n=f/n*e;
if(n%m==0) //能除整
printf("%lld\n",n/m);
else //不能整除,要化簡後，輸出分數
{
k=gcd(m,n); //求分子分母最大公約數
printf("%lld/%lld\n",n/k,m/k);
}
}
return 0;
}
