ACM 数论 Maximum GCD

爱被打了一巴掌 2022-06-10 03:40 276阅读 0赞

滴，集训第二十三天打卡。

转眼集训已经过去一半了，今天是数论基础。

一眼看去，都是简单题，

一题题做来，都是坑啊坑…

UVA 11827 Maximum GCD

20170809143733845

题目大意：求给定的一组数中，两两之间最大的GCD。

思路：这道题猛地一眼看，就是找一下GCD，一个函数可以搞定。但是输入就有失公正了…输入两个数之间的空格不一定只有一个，所以要用gets读入在一个个取出来…

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. using namespace std;
  5. char s[3000];
  6. int a[102];
  7. int gcd(int a,int b)
  8. {
  9.     return b?gcd(b,a%b):a;
  10. }
  11. int main()
  12. {
  13.     int n,i,j,len,u,sum,ans;
  14.     scanf("%d",&n);
  15.     getchar();
  16.     while(n--)
  17.     {
  18.         gets(s);
  19.         len=strlen(s);
  20.         u=0;
  21.         for(i=0;i<len;i++)
  22.         {
  23.             sum=0;
  24.             while(i<len&&s[i]!=' ')
  25.             {
  26.                 sum=sum*10+s[i]-'0';
  27.                 i++;
  28.             }
  29.             a[u++]=sum;
  30.         }
  31.         ans=0;
  32.         for(i=0;i<u;i++)
  33.         {
  34.             for(j=i+1;j<u;j++)
  35.                ans=max(ans,gcd(a[i],a[j]));
  36.         }            
  37.         printf("%d\n",ans);
  38.     }
  39. }

发表评论

表情：
评论列表 （有 0 条评论，276人围观）

还没有评论，来说两句吧...

相关阅读