小波的GCD

NC212587. 小波的GCD

描述

小波有一个大小为n的数组，小波不喜欢很大的数，他想尽可能使数组的和尽可能小，现在只有一种使数组变小的办法，若数字c为数组中每一个数的因数的话，那么便可以数组中的所有数都除以c，小波想知道最小的数组的和，你能帮帮他吗。

输入描述

第一行一个整形数 。

第二行，n个整形数 。

输出描述

输出一个整形数，表示答案。

示例1

输入:

5
6 36 18 30 42

输出:

说明:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 387ms, 内存消耗: 4160K, 提交时间: 2022-03-03 22:12:42

#include<bits/stdc++.h>
using namespace std;
int n,t,a[1000006];
long long sum=0;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    t=a[0];
    for(int i=1;i<n;i++)
        t=__gcd(t,a[i]);
    for(int i=0;i<n;i++)
        sum+=a[i]/t;
    cout<<sum<<endl;
}

上一题

下一题

详情