首页 > 代码库 > NYOJ 948 Max Gcd

NYOJ 948 Max Gcd

2024-07-17 05:51:29   211人阅读

思路：不要死套路来一个一个暴力求最大公约数，换个思路，从最大的数开始，进行除法操作，如果有两个满足条件的数，那么就是这个数就是最大的了。方法很巧

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=948

代码

#include <stdio.h>#include <algorithm>using namespace std; int max;int e[100001];int main(){    int n;    int count;    int temp;//记号，看是否达到两个    int flag;//标志，无用    while(scanf("%d",&n)!=EOF)    {        flag = 0;        temp = 0;        count=0;        for(int i=1;i<=n;i++)        {            scanf("%d",e+i);            count++;        }                sort(e+1,e+n+1);            for(int i=e[n];i>=1;i--)        {            for(int j = count;j>=1;j--)            {                if(e[j]%i==0)                    temp++;                if(temp==2)                {                    flag = 1;                    break;                }            }             temp = 0;            if(flag ==1 )            {                printf("%d\n",i);                break;            }        }     }    return 0;}

 


联系
我们