ZZULIOJ 1879: 蛤玮买好了礼物【数学】

╰+攻爆jí腚メ 2022-07-30 14:58 104阅读 0赞

## 1879: 蛤玮买好了礼物 ##

Time Limit: 1 Sec Memory Limit: 128 MB  
Submit: 395 Solved: 146  
  
[Submit][] [Status][] [Web Board][]

## Description ##

蛤玮的妹子过生日,蛤玮把千辛万苦挑选出来的礼物送到了妹子面前,然而妹子非常生气,因为妹子要的是化妆套装,而蛤玮买了一套水彩铅笔,更可气的是这些铅笔像是二手的,因为他们不是一样长!  
为了惩罚蛤玮,妹子说"我有强迫症,受不了这些铅笔不一样长,你快去搞定它!不然就买化妆套给我!".  
还好，这些铅笔的长度都是整数，蛤玮灵机一动,可以把些铅笔掰断使得它们可以一样长，当然要保证铅笔尽可能的长。 那么当这些铅笔最终一样长的时候,一共有多少支铅笔?

## Input ##

**T(1<=T<=100),表示数据组数.**

**每组数据第一行一个整数n(1<=n<=100),表示蛤玮买来的铅笔个数,接下来一行n个整数,表示n个铅笔的长度.保证长度都为正整数且小于1e7.**

## Output ##

**每组数据输出一行,表示最终的铅笔个数.**

## Sample Input ##

2 3

4 6 14

## Sample Output ##

## HINT ##

对于第一个输入，最终掰成了5个长度为1的铅笔，第二个输入，最终掰成了12个长度为2的铅笔。

解题思路：

找出和，除以他们的最大公约数。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int gcd(int a, int b)
    {
            if(!b) return a;
            else  return gcd(b, a%b );
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n;
            scanf("%d",&n);
            if(n==1)
            {
                int op;
                scanf("%d",&op);
                printf("1\n");
                continue;
            }
            int i,j;
            int sum=0;
            int xx,yy;
            scanf("%d",&xx);
            scanf("%d",&yy);
            int ans=gcd(xx,yy); 
            sum+=(xx+yy);
            for(i=0;i<n-2;i++)   
            {
                int pp;
                scanf("%d",&pp);
                sum+=pp;
                ans=gcd(ans,pp);
            }
            printf("%d\n",sum/ans);
        }
        return 0;
    }
    /**************************************************************
        Problem: 1879
        User: qinyuxiang
        Language: C++
        Result: Accepted
        Time:1 ms
        Memory:872 kb
    ****************************************************************/

[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?id=1879
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1879
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1879