Codeforces - 346A - Alice and Bob

http://codeforces.com/problemset/problem/346/A

观察了一下，猜测和他们的最大公因数有关，除以最大公因数前后结果是不会变的。

那么怎么证明一定是有n轮呢？我猜就是因为现在至少有几个是互质的，所以总是可以构造出1？具体怎么证明呢？还是看看别人的思路吧……

首先最终停止的状态一定是一个等差数列，这个是毫无疑问的。设首项为d，那么肯定停止于d,2d,3d,...,n，那么很显然d就是他们的最大公因数啊……对哦？！

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int n;

int a[];

int main(){

    scanf("%d",&n);

    for(int i=;i<n;i++){

        scanf("%d",&a[i]);

    }

    int g=a[];

    for(int i=;i<n;i++){

        g=__gcd(g,a[i]);

    }

    for(int i=;i<n;i++){

        a[i]/=g;

    }

    int maxa=*max_element(a,a+n);

    int d=maxa-n;

    if(d%)

        puts("Alice");

    else

        puts("Bob");

}

巴特西

Codeforces - 346A - Alice and Bob - 简单数论

最新文章

热门文章