ACM 数论 Maximum GCD

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

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

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

一眼看去，都是简单题，

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

**UVA 11827 Maximum GCD**

**![20170809143733845][]**

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

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

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char s[3000];
    int a[102];
    int gcd(int a,int b)
    {
        return b?gcd(b,a%b):a;
    }
    int main()
    {
        int n,i,j,len,u,sum,ans;
        scanf("%d",&n);
    	getchar();
        while(n--)
    	{
            gets(s);
            len=strlen(s);
            u=0;
            for(i=0;i<len;i++)
    		{
                sum=0;
                while(i<len&&s[i]!=' ')
    			{
                    sum=sum*10+s[i]-'0';
                    i++;
                }
                a[u++]=sum;
            }
            ans=0;
            for(i=0;i<u;i++)
    		{
    			for(j=i+1;j<u;j++)
       			ans=max(ans,gcd(a[i],a[j]));
    		}            
            printf("%d\n",ans);
        }
    }

[20170809143733845]: /images/20220610/8b7c42e38cde449ca971decf03522f8f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，175人围观）

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

相关阅读

相关 O - GCD - Extreme (II)————欧拉函数+数论基本定理

题目要求： [链接][Link 1] ![在这里插入图片描述][20190908174415651.png] 题目给你一个N，让你求如图这个G。其实...

Love The Way You Lie/ 2024年04月18日 15:08/ 0 赞/ 78 阅读

相关【数论】hdu 5019 Revenge of GCD

[Problem - 5019 (hdu.edu.cn)][Problem - 5019 _hdu.edu.cn] 题意：给出整数x、y、k，求x、y的第k大公约数。

小灰灰/ 2024年03月30日 11:46/ 0 赞/ 68 阅读

相关 Hdu 1695 GCD (数论容斥原理)

参考了：[HDU 1695 GCD 【数论，容斥原理】 - 脑残 - 博客频道 - CSDN.NET][HDU 1695 GCD _ - _ - _ - CSDN.NET]

落日映苍穹つ/ 2022年08月26日 08:10/ 0 赞/ 160 阅读

相关 Maximum GCD + ungetc()函数的使用

Maximum GCD : [http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329\problem/F][h

你的名字/ 2022年08月21日 04:49/ 0 赞/ 129 阅读

相关 A/B（数论水题） hdu ACM 1576 c++

A/B Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Other

太过爱你忘了你带给我的痛/ 2022年08月11日 03:28/ 0 赞/ 164 阅读

相关 Uva——11827 Maximum gcd

这一题的主要是考察读入数据的技巧，其余的好像就没有了. 关于int ungetc(char c, FILE \stream); Parameters charact

迷南。/ 2022年08月10日 15:53/ 0 赞/ 21 阅读

相关（ACM数论）中国剩余定理（孙子定理）

中国剩余定理是一种能求解一次同余方程组的姿势~ 首先我们来看看什么是一次同余方程组： X % a\[1\] = b\[1\] X % a\[2\] = b\[2\] …

素颜马尾好姑娘i/ 2022年07月17日 03:27/ 0 赞/ 247 阅读

相关 ACM 数论 Maximum GCD

滴，集训第二十三天打卡。转眼集训已经过去一半了，今天是数论基础。一眼看去，都是简单题，一题题做来，都是坑啊坑... UVA 11827 Maximum

爱被打了一巴掌/ 2022年06月10日 03:40/ 0 赞/ 176 阅读

相关 acm数论之欧几里得gcd

1.欧几里得定理 1. 同余定理的公式：(a+b)%mod=(a%mod+b%mod)%mod 2. (a\b)%mod=(a%mod\b%mod)%mod

叁歲伎倆/ 2021年12月15日 04:07/ 0 赞/ 345 阅读

相关 HDU - 2504- 又见GCD【数论+gcd 】题解

目录 1.题目 2.代码 1.题目有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a

逃离我推掉我的手/ 2021年07月25日 00:03/ 0 赞/ 380 阅读