丰满少妇高潮无套内谢,国产精品普通话国语对白露脸,极品白嫩少妇无套内谢

最大公約數（二）

【例1】最小公倍數。

問題描述

求n個數的最小公倍數。

輸入

輸入將包含多組測試用例。輸入的第一行將包含一個整數，指示測試用例的數量。每個測試用例將由m n1 n2 n3…nm形式的單行組成，其中m是集合中的整數數，n1…nm是整數。所有整數都是正的，并且在32位整數的范圍內。

輸出

對于每個測試用例，輸出包含相應LCM的單行。所有結果都將在32位整數的范圍內。

輸入樣例

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，每組測試數據占一行。

輸入樣例

6 2

12 4

輸出樣例

（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

輸出樣例

（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

輸出樣例

（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；

每組輸出占一行，具體輸出格式參見樣例。

輸入樣例

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并不一定是按等差數列中的順序給出）。

輸出

輸出一個整數表示答案。

輸入樣例

2 6 4 10 20

輸出樣例

（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

輸出樣例

（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）編程思路。

設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表示可能的起始網格數。

輸入樣例

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

參考程序

【練習2】HDU 1222 Wolf and Rabbit （http://acm.hdu.edu.cn/showproblem.php?pid=1222）。

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

參考程序

【練習3】HDU 1713 相遇周期（http://acm.hdu.edu.cn/showproblem.php?pid=1713）。

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

參考程序

【練習4】HDU 2104 hide handkerchief （http://acm.hdu.edu.cn/showproblem.php?pid=2104）。

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

參考程序

【練習5】HDU 2503 a/b + c/d （http://acm.hdu.edu.cn/showproblem.php?pid=2503）。

#include <stdio.h>
int gcd(int m,int n)
{
    int r=m%n;
    while (r!=0){
        m=n;
        n=r;
        r=m%n;
    }
    return n;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b,c,d,x,y;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        x=a*d+b*c;
        y=b*d;
        printf("%d %d\n",x/gcd(x,y),y/gcd(x,y));
    }
    return 0;
}

參考程序

【練習6】HDU 4497 GCD and LCM （http://acm.hdu.edu.cn/showproblem.php?pid=4497）。

#include <stdio.h>
int main()
{
    int prim[65545],pcnt=0;
    int vis[65545]={0};
    int i,j;
    prim[pcnt++]=2;                  // 最小的質數為2
    for (i=4;i<65540;i+=2) vis[i]=1;      // 將2的倍數全篩掉
    for (i=3;i<65540;i+=2)
    {
        if (vis[i]==0)                 // i在篩子中沒有篩掉，是質數
        {
            prim[pcnt++]=i;
            for (j=3;i*j<65540;j+=2)
                vis[i*j]=1;
        }
    }
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int gcd, lcm;
        scanf("%d%d", &gcd, &lcm);
        if (lcm % gcd != 0)
        {
            printf("0\n");
            continue;
        }
        int m = lcm / gcd;
        int ans = 1;
        for (i = 0; prim[i] * prim[i] <= m; i++)
        {
            if (m % prim[i] == 0)
            {
                int cnt = 0;
                while (m % prim[i] == 0)
                {
                    cnt++;
                    m /= prim[i];
                }
                ans *= 6 * cnt;
            }
        }
        if (m > 1) ans *= 6;
        printf("%d\n", ans);
    }
    return 0;
}

參考程序

【練習7】 HDU 5175 Misaki's Kiss again （http://acm.hdu.edu.cn/showproblem.php?pid=5175）。

// 求滿足gcd(N,M)=N xor M的M的個數與值。
// 若a xor b = c，那么a xor c = b
// 設 gcd(N,M)==N xor M=k，顯然一定k是N的約數
// 由N xor M=k，可得  M=N xor K
// 由此 gcd(N,M)= gcd(N,N xor K) =k
// 枚舉N的所有約數，再判斷gcd(N,N xor K)是不是等于K就行了。
#include <stdio.h>
long long s[1000005];
long long gcd(long long a,long long b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int main()
{
    int iCase=0;
    long long n,m,i;
    while (scanf("%lld",&n)!=EOF)
    {
       int k=0;
       for (i=1;i*i<=n;i++)
       {
          if (n%i!=0) continue;
          m=i^n;
          if (m && m<=n && gcd(m,n)==i)
             s[k++]=m;
          m=(n/i)^n;
          if (m && m<=n && gcd(m,n)==n/i)
             s[k++]=m;
       }
       if (k==0)
       {
           printf("Case #%d:\n0\n\n",++iCase);
           continue;
       }
       int x,y;
       for (x=0;x<k-1;x++)
            for (y=0;y<k-1-x;y++)
               if (s[y]>s[y+1])
               { m=s[y]; s[y]=s[y+1]; s[y+1]=m; }
       int len=1;
       for (x=1;x<k;x++)
          if (s[x]!=s[len-1]) s[len++]=s[x];
       printf("Case #%d:\n%d\n",++iCase,len);
       printf("%lld",s[0]);
       for (x=1;x<len;x++)
           printf(" %lld",s[x]);
       printf("\n");
    }
    return 0;
}

參考程序

【練習8】HDU 5512 Pagodas （http://acm.hdu.edu.cn/showproblem.php?pid=5512）。

#include <stdio.h>
int gcd(int a,int b)
{
    if (a%b==0) return b;
    return gcd(b, a%b);
}
int main ()
{
    int t,iCase=0;
    scanf("%d", &t);
    while (t--)
    {
        int n, a, b;
        scanf("%d%d%d", &n, &a, &b);
        printf("Case #%d: ", ++iCase);
        int d = n / gcd(a, b);
        if (d%2) printf("Yuwgna\n");
        else printf("Iaka\n");
    }
    return 0;
}

參考程序

【練習9】HDU 6025 Coprime Sequence （http://acm.hdu.edu.cn/showproblem.php?pid=6025）。

#include <stdio.h>
int a[100005];
int pre[100005],nxt[100005];   // 前綴gcd 和 后綴gcd
int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int i,j;
        for (i=0;i<n;i++)
            scanf("%d",&a[i]);
        pre[0] = a[0];
        nxt[n-1] = a[n-1];
        for (i=1;i<n;i++)
            pre[i] = gcd(pre[i-1],a[i]);  // 前綴gcd
        for (i=n-2;i>=0;i--)
            nxt[i] = gcd(nxt[i+1],a[i]);  // 后綴gcd
        int ans =nxt[1];                 // 去掉第1個數a[0]后的gcd
        for (i=1;i<=n-2;i++)             // 依次去掉中間n-2個數后的gcd
            ans=max(ans,gcd(pre[i-1],nxt[i+1]));
        ans = max(ans,pre[n-2]);         // 去掉最后1個數a[n-1]后的gcd
        printf("%d\n",ans);
    }
    return 0;
}

參考程序

posted on 2022-12-20 10:40 aTeacher 閱讀(366) 評論(0) 收藏舉報

刷新頁面返回頂部

I am a teacher!

導航

公告

最大公約數（二）