URAL 1053 Pinocchio

URAL_1053

    找了几个例子算了一下，发下对于两个不等的长度，最后会变成的长度等于他们的最大公约数。

    后来突然意识到，题目中给的操作就是不断地在使用辗转相除，所以最后得到的结果当然就是两个数的最大公约数了。

#include<stdio.h>
#include<string.h>
#define MAXD 1010
int N, a[MAXD];
int gcd(int x, int y)
{
    return y == 0 ? x : gcd(y, x % y);
}
void init()
{
    int i;
    for(i = 1; i <= N; i ++)
        scanf("%d", &a[i]);
}
void solve()
{
    int i;
    for(i = 1; i <= N; i ++)
        a[i + 1] = gcd(a[i], a[i + 1]);
    printf("%d\n", a[N]);
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
        solve();
    }
    return 0;
}