hdu 5207 Greatest Greatest Common Divisor（筛法求公约数）-白红宇

hdu 5207 Greatest Greatest Common Divisor（筛法求公约数）

阅读量：5273 次

发布时间：2019-06-14

本文共 1258 字，大约阅读时间需要 4 分钟。

题意：给定一组数，取两个数，使得gcd最大

思路：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define ll __int64//#define ll long longint vis[100000+100];int gcd(int a,int b){    return a%b==0?b:gcd(b,a%b);}int main(){    int t,n,ans;    int temp;    int i,j,k;    int cas=1;    scanf("%d",&t);    while(t--)    {        ans=0;        int maxx=0;        memset(vis,0,sizeof(vis));        scanf("%d",&n);        for(i=0;i
         
          maxx) maxx=temp;        }        for(i=100000;i>=1;i--)        {            int cnt=0;            /*if(i==1)            {                printf("max:%d\n",maxx);                for(j=i;j<=maxx;j+=i)               {                if(vis[i]!=0) cnt+=vis[j];                printf("cnt:%d j:%d vis:%d\n",cnt,j,vis[j]);                if(cnt>=2){  break;}               }            }*/            for(j=i;j<=maxx;j+=i)            {                if(vis[j]!=0) cnt+=vis[j];                if(cnt>=2){  break;}            }            if(cnt>=2)            {                ans=i;                break;            }        }        printf("Case #%d: %d\n",cas++,ans);    }    return 0;}