【例1】最小公倍数。

问题描述

求n个数的最小公倍数。

输入

输入将包含多组测试用例。输入的第一行将包含一个整数，指示测试用例的数量。每个测试用例将由m n1 n2 n3…nm形式的单行组成，其中m是集合中的整数数，n1…nm是整数。所有整数都是正的，并且在32位整数的范围内。

输出

对于每个测试用例，输出包含相应LCM的单行。所有结果都将在32位整数的范围内。

输入样例

2

3 5 7 15

6 4 10296 936 1287 792 1

 输出样例

105

10296

         （1）编程思路。

         先求第一个和第二个元素的最小公倍数，然后拿求得的最小公倍数和第三个元素求最小公倍数，继续下去，直到求取了全部元素的最小公倍数。

         在通过最大公约数求最小公倍数的时候，先除再乘，避免溢出。

        （2）源程序。

#include <stdio.h>
int gcd(int a,int b)
{
    if (a%b==0) return b;
    return gcd(b, a%b);
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        int ans=1,tmp;
        int x;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            tmp=ans/gcd(ans,x)*x;  // 先除后乘，避免溢出
            ans=tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}

        将上面的源程序提交给HDU题库 HDU 1019 Least Common Multiple （http://acm.hdu.edu.cn/showproblem.php?pid=1019），可以Accepted。

【例2】又见GCD。

问题描述

有三个正整数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）编程思路。

          因为a和c的最大公约数为b，显然c肯定是b的倍数，从c=2b开始穷举，找到第1个c=kb，满足gcd(a,c)==b 就是所求的答案。

        （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;
}

         将上面的源程序提交给HDU题库 HDU 2504 又见GCD （http://acm.hdu.edu.cn/showproblem.php?pid=2504），可以Accepted。

【例3】最小的数。

问题描述

一个正整数N除以M1余(M1 - a)，除以M2余(M2-a), 除以M3余(M3-a),总之， 除以MI余(MI-a),其中（a<Mi<100 i=1,2,…I）,求满足条件的最小的数。

输入

输入数据包含多组测试实例，每个实例的第一行是两个整数I(1<I<10)和a，其中，I表示M的个数，a的含义如上所述，紧接着的一行是I个整数M1,M1...MI，I=0 并且a=0结束输入，不处理。

输出

对于每个测试实例，请在一行内输出满足条件的最小的数。每个实例的输出占一行。

输入样例

2 1

2 3

0 0

输出样例

5

        （1）编程思路。

         设所求的最小数为n，

         由n%m1=m1-a，==>n%m1+a=m1，即n+a≡0(mod m1)，也就是（n+a）是m1的倍数；

         同理，（n+a）是m2的倍数，…，（n+a）也是mi的倍数。

         因此，n就是所有mi的最小公倍数，再减去a。

        （2）源程序。 

#include <stdio.h>
long long gcd(long long a,long long b)
{
    if (a%b==0) return b;
    return gcd(b, a%b);
}
int main()
{
    int n;
    long long a,m,ans;
    while (scanf("%d%lld",&n,&a) && (n||a))
    {
        ans=1;
        while (n--)
        {
            scanf("%lld",&m);
            ans=m/gcd(ans,m)*ans;
        }
        printf("%lld\n",ans-a);
    }
    return 0;
}

        将上面的源程序提交给HDU题库 HDU 1788 Chinese remainder theorem again （http://acm.hdu.edu.cn/showproblem.php?pid=1788），可以Accepted。

【例4】切蛋糕。

问题描述

一次生日Party可能有p人或者q人参加，现准备有一个大蛋糕。问最少要将蛋糕切成多少块(每块大小不一定相等)，才能使p人或者q人出席的任何一种情况，都能平均将蛋糕分食。

例如，当有2人或3人出席时，将蛋糕切成大小分别为1/3、1/3、1/6、1/6的四块即满足要求。

当2个人来时，每人可以吃1/3+1/6=1/2，1/2块。

当3个人来时，每人可以吃1/6+1/6=1/3，1/3，1/3块。

输入

每行有两个数p和q。

输出

输出最少要将蛋糕切成多少块.

输入样例

2 3

输出样例

4

        （1）编程思路。

        先把蛋糕切 p刀等分成p份（每切一刀从边缘切到蛋糕中心点），然后把蛋糕拼在一起，从前面p刀的某一切线开始，再切q刀等分成q份。

        两次切法会有重复部分，减去重复的部分就是gcd(p,q)。

        （2）源程序。

#include <stdio.h>
int gcd(int a,int b)
{
    if (a%b==0) return b;
    return gcd(b, a%b);
}
int main()
{
    int p,q;
    while (scanf("%d%d",&p,&q)!=EOF)
    {
        printf("%d\n",p+q-gcd(p,q));
    }
    return 0;
}

        将上面的源程序提交给HDU题库 HDU 1722 Cake （http://acm.hdu.edu.cn/showproblem.php?pid=1722），可以Accepted。

【例5】猜生日。

问题描述

小明对生日十分看重，因为他可以得到祝福，可以和朋友亲人一起分享快乐，可以为自己的人生做一次总结，并且...能够收到好多礼物！

不过小明是个神秘的人，不会轻易告诉你他的生日，现在他想到一个办法，让你去猜他的生日是哪一天。

 小明会告诉你如下三个信息：

1. 出生月份和出生日子的最大公约数；

2. 出生月份和出生日子的最小公倍数；

3. 出生年份；

现在要求你猜出小明的生日。

输入

第一行输入一个正整数T，表示总共有T组测试数据(T <= 200)；

对于每组数据依次输入三个数x，y，z，

x表示出生月份和出生日子的最大公约数(1<= x <=1000)；

y表示出生月份和出生日子的最小公倍数(1<= y <=1000)；

z表示出生年份（1900 <= z <= 2013）。

每组输入数据占一行。

输出

对于每组数据，先输出Case数。

如果答案不存在 ，输出“-1”；

如果答案存在但不唯一 ，输出“1”；

如果答案唯一，输出生日，日期格式为YYYY/MM/DD；

每组输出占一行，具体输出格式参见样例。

输入样例 

3

12 24 1992

3 70 1999

9 18 1999

输出样例

Case #1: 1992/12/24

Case #2: -1

Case #3: 1999/09/18

        （1）编程思路。

          对月份month从1~12进行穷举即可。除了求最大公约数和最小公倍数外，还需注意闰年的处理。

        （2）源程序。

#include <stdio.h>
int gcd(int a,int b)
{
    if (a%b==0) return b;
    return gcd(b, a%b);
}
int isLeap(int year)    // 闰年判断
{
   if((year%4==0 && year%100)||(year%400==0))  return 1;
   else return 0;
}
int month[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},
                  {0,31,29,31,30,31,30,31,31,30,31,30,31}};
int main()
{
    int t,iCase=0;
    scanf("%d",&t);
    while(t--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        printf("Case #%d: ",++iCase);
        int i,j,flag=0;
        int mon,day;
        for (i=x;i<=12;i++)
        {
           if (x*y%i==0)
           {
               j=x*y/i;
               if (gcd(i,j)==x && j<=month[isLeap(z)][i])
               {
                   day=j;
                   mon=i;
                   flag++;
               }
           }
        }
        if (flag==0)
             printf("-1\n");
        else if (flag==1)
             printf("%d/%02d/%02d\n",z,mon,day);
        else
             printf("1\n");
    }
    return 0;
}

        将上面的源程序提交给HDU题库 HDU 4551 生日猜猜猜 （http://acm.hdu.edu.cn/showproblem.php?pid=4551），可以Accepted。

【例6】等差数列。

问题描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N个整数。

现在给出这N个整数，小明想知道包含这N个整数的最短的等差数列有几项？

例如，给出2,6,4,10,20这5个数，则包含这5个数的最短的等差数列是 2,4,6,8,10,12,14,16,18,20，共有10项。

输入

输入的第一行包含一个整数N（2≤N≤10⁵）。

第二行包含N个整数A1,A2,…,AN。（0≤Ai≤10⁹，另外A1 ∼ AN并不一定是按等差数列中的顺序给出）。

输出

输出一个整数表示答案。

输入样例

5

2 6 4 10 20

输出样例

10

        （1）编程思路。

         将输入的n个数按从小到大的顺序排列。显然，等差数列的首项为a[0]，末项为a[n-1]。相邻两项间共有n-1个差值（a[i]-a[i-1]），显然数列的公差d是这n-1个差值的最大公约数。求得了公差d后，等差数列的项数就可以求出了。设项数为ans，有a[n-1]=a[0]+(ans-1)*d，所以ans=(a[n-1]-a[0])/d+1。

        （2）源程序。

#include <stdio.h>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
    if (a%b==0) return b;
    return gcd(b, a%b);
}
int main ()
{
    int n;
    scanf("%d", &n);
    int i,a[100005];
    for (i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    int d=a[0]-a[1];
    if (d==0) 
        printf("%d\n",n);
    else
    {
        for (i=2;i<n;i++)
           d=gcd(d,a[i]-a[i-1]);
        printf("%d\n",(a[n-1]-a[0])/d+1);
    }
    return 0;
}

       将上面的源程序提交给洛谷题库 P8682 [蓝桥杯 2019 省 B] 等差数列 （https://www.luogu.com.cn/problem/P8682），可以Accepted。

 【例7】买玫瑰花。

问题描述

小明想买N朵玫瑰花，他面前有两家花店，每一家店有无数朵玫瑰花，但是他们按束卖。第一家店一束花里有A朵，每一束花要用B块钱。第二家店一束花里有C朵，每一束花要用D块钱。

求小明至少买N朵花最少需要花多少钱。

输入

一行五个整数 N,A,B,C,D，意义见题目所述。

输出

一行一个整数代表最小花费。

输入样例

5 1 4 3 6

输出样例

12

      （1）编程思路。

        1家花店b元可以买a朵，1家花店d元可以买c朵，设b/a<d/c（即b*c<a*d），若不满足条件，则分别交换a和c，交换b和d。这样一束a朵花卖得便宜些，先全部在这个花店买够n朵花。然后再枚举到贵的花店更换i束花后的花费来进行比较，取花费较少的方案。枚举的最大值为gcd(a,c)。

        （2）源程序。

#include <stdio.h>
long long gcd(long a,long b)
{
    if (a%b==0) return b;
    return gcd(b, a%b);
}
int main()
{
    long long n,a,b,c,d,t,ans;
    scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
    if (b*c < a*d)                        // 若第1家花店的花便宜些
    {
        t=a; a=c; c=t;
        t=b; b=d; d=t;
    }
    ans = (n + c - 1) / c * d;            // 先全部到最便宜的花店买花
    long long i;
    for (i = c/gcd(a,c); i >= 0; i--)     // 枚举到贵的花店买i束花进行替换的代价
    {
        t = i * b;
        if (n - i * a >= 0)
            t = t + (n - i * a + c - 1) / c * d;
        if (ans>t) ans=t;
    }
    printf("%lld\n",ans);
    return 0;
}

        将上面的源程序提交给洛谷题库 P6767 [BalticOI 2020/2012 Day0] Roses （https://www.luogu.com.cn/problem/P6767） ，可以Accepted。

【例8】区间GCD。

问题描述

给定一行n个正整数a[1]..a[n]。

m次询问，每次询问给定一个区间[L,R]，输出a[L]..a[R]的最大公因数。

输入

第一行两个整数n，m（1 <= n <= 1000，1 <= m <= 1,000,000）。

第二行n个整数表示a[1]..a[n]（0 < a[i] <= 1,000,000,000）。

以下m行，每行2个整数表示询问区间的左右端点。

保证输入数据合法。

输出

共m行，每行表示一个询问的答案。

输入样例

5 3

4 12 3 6 7

1 3

2 3

5 5

输出样例

1

3

7

      （1）编程思路。

        设f[i][j]表示区间[i,j]中的最大公因数gcd，则有

        f[i][j]=gcd(f[i][i],f[i+1][j])

        边界f[i][i]=itself。

        （2）源程序。 

#include <stdio.h>
int gcd(int a,int b)
{
    if (a%b==0) return b;
    return gcd(b, a%b);
}
int f[1005][1005];
int main ()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int i,j;
    for (i=1;i<=n;i++)
        scanf("%d",&f[i][i]);
    for (i=n-1;i>=1;i--)
       for (j=i+1;j<=n;j++)
           f[i][j]=gcd(f[i][i],f[i+1][j]);
    for (i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",f[l][r]);
    }
    return 0;
}

         将上面的源程序提交给洛谷题库 P1890 gcd区间 （https://www.luogu.com.cn/problem/P1890） ，可以Accepted。

【例9】青蛙的跳跃。

问题描述

一只青蛙在一个有无限行和无限列的网格地图进行跳跃。青蛙从格子（sx，sy），开始它的旅程。青蛙用了一种特殊的跳跃方式。如果青蛙目前处于网格（x，y），首先，它将找到可以被x和y除的最小z（z是x、y的最小公倍数），并精确地向上或向右跳z步。因此，下一个可能的网格将是（x+z，y）或（x，y+z）。

经过有限的步数（可能为零）后，青蛙终于跳到了网格（ex，ey）。然而，它太累了，忘记了起跑线的位置！

请告诉青蛙可以到达的可能的起始格子数。

输入

第一行包含一个整数T（1≤T≤1000），表示测试用例的数量。

每个测试用例包含两个整数ex和ey（1≤ex，ey≤109），这是目标网格。

输出

对于每个测试用例，应该输出“case#x:y”，其中x表示用例编号，从1开始计数，y表示可能的起始网格数。

输入样例

3

6 10

6 8

2 8

输出样例

Case #1: 1

Case #2: 2

Case #3: 3

        （1）编程思路。

        假设x、y的最大公约数gcd(x,y)=k，那么不妨设x=p*k，y=q*k（p与q互质）

        x和y的最小公倍数z=p*q*k，即跳到的新网格点为（p*k+p*q*k，q*k）或（p*k，q*k+p*q*k）。

        新得到的点的最小公倍数

         gcd(p*k+p*q*k，q*k)=gcd(p*(q+1)*k，q*k)

         因为q和p是互质的，q和q+1也是互质的，因此gcd(p*k+p*q*k，q*k)=k。

        同理，gcd(p*k，q*k+p*q*k)=k。

        也就是说，青蛙跳过的各点都有相同的最大公约数，可以利用这一点来根据终点逆推求解原先的起点。

        （2）源程序。

#include <stdio.h>
int gcd(int x,int y)
{
    if (x%y==0) return y;
    return gcd(y,x%y);
}
int main()
{
    int t,iCase=0;
    scanf("%d",&t);
    while (t--)
    {
        int ans=1;
        int x,y,tmp;
        scanf("%d%d",&x,&y);
        if (x>y)    // 跳跃后，小的坐标值是不变的
        {  tmp=x;  x=y;  y=tmp; }
        int k=gcd(x,y);
        while (y%(x+k)==0)
        {
             ans++;
             y=y/(x/k+1);
             if (x>y)
             { tmp=x;  x=y;  y=tmp; }
             k=gcd(x,y);
         }
         printf("Case #%d: %d\n",++iCase,ans);
    }
    return 0;
}

         将上面的源程序提交给HDU 题库 HDU 5584 LCM Walk （http://acm.hdu.edu.cn/showproblem.php?pid=5584） ，可以Accepted。

 【练习1】HDU 1014 Uniform Generator （http://acm.hdu.edu.cn/showproblem.php?pid=1014）。

#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;
}

参考程序

#include <stdio.h>
int gcd(int a,int b)
{
    int r=a%b;
    while (r!=0){
        a=b; b=r; r=a%b;
    }
    return b;
}
int main()
{
    int t;scanf("%d",&t);
    while (t--)
    {
        int m,n;
        scanf("%d%d",&m,&n);
        if (gcd(m,n)==1)
           printf("NO\n");
        else
           printf("YES\n");
    }
    return 0;
}