codeforces 389A. Fox and Number Game

男娘i 2022-08-10 06:10 10阅读 0赞

题目链接\[CF 389A.\] ([http://codeforces.com/problemset/problem/389/A][http_codeforces.com_problemset_problem_389_A])：  
题目描述：  
A. Fox and Number Game  
time limit per test1 second  
memory limit per test256 megabytes  
inputstandard input  
outputstandard output  
Fox Ciel is playing a game with numbers now.

Ciel has n positive integers: x1, x2, …, xn. She can do the following operation as many times as needed: select two different indexes i and j such that xi > xj hold, and then apply assignment xi = xi - xj. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.

Input  
The first line contains an integer n (2 ≤ n ≤ 100). Then the second line contains n integers: x1, x2, …, xn (1 ≤ xi ≤ 100).

Output  
Output a single integer — the required minimal sum.

Sample test(s)  
input  
2  
1 2  
output  
2  
input  
3  
2 4 6  
output  
6  
input  
2  
12 18  
output  
12  
input  
5  
45 12 27 30 18  
output  
15  
Note  
In the first example the optimal way is to do the assignment: x2 = x2 - x1.

In the second example the optimal sequence of operations is: x3 = x3 - x2, x2 = x2 - x1.

言简意赅：  
此题题意为可以连续多次利用ai=ai-aj，直到把ai中的每一个数变成最小且相等时，既满足题意中的条件不再能进行操作了，所以可以借助于直接暴力的代码进行实现.

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    int a[105];
    int main()
    {
        int n;
        int flag;
        while(scanf("%d",&n)!=EOF)
        {
            flag=0;
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            while(1)
            {
                sort(a,a+n,greater<int>());
                flag=0;
                for(int i=0;i<n-1;i++)
                {
                    if(a[i]>a[i+1])
                    a[i]=a[i]-a[i+1];
                    else flag++;
                }
                if(flag==n-1)
                break;
            }
            printf("%d\n",n*a[0]);
        }
        return 0;
    }

当然此题的本意可以简化为要去求解所有数的最大公约数的问题，代码实现如下：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    int gcd(int a,int b)
    {
        if(!b)
        return a;
        else return gcd(b,a%b);
    }
    
    int a[105];
    int main()
    {
        int n;
        int k;
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=0; i<n; i++)
            {
                scanf("%d",&a[i]);
            }
            k=gcd(a[0],a[1]);
            for(int i=2; i<n; i++)
            {
                k=gcd(k,a[i]);
            }
        printf("%d\n",n*k);
        }
        return 0;
    }

如果代码还不能A掉，那就不能去睡觉。

[http_codeforces.com_problemset_problem_389_A]: http://codeforces.com/problemset/problem/389/A