Candy's Candy Solution (CT S02E11, Problem C)

//Solution by sandyeep
#include <bits/stdc++.h>
using namespace std;

long long n, a[100100], f, gcd, ans, mn;
vector<long long> factors;

void jain()
{
    gcd = 0;
    for(int i=0; i<n; i++)  {
        cin >> a[i];
        gcd = __gcd(gcd, a[i]);
    }
    factors.clear();
    for(int i=1; i * i <= gcd; i++) {
        if(gcd % i == 0)    {
            factors.push_back(i);
            if(i * i != gcd)    {
                factors.push_back(gcd / i);
            }
        }
    }
    sort(factors.begin(), factors.end());
    ans = 0;
    for(auto k : factors)   {
        bool ok = true;
        long long rem = (a[0] / k) % n;
        mn = (a[0] / k - 1) / n;
        for(int i=1; i < n; i++)    {
            if((a[i] / k) <= n or ((a[i] / k) % n) != rem)  {
                ok = false;
            }
            mn = min(mn, (a[i] / k - 1) / n);
        }
        if(ok)  {
            ans += mn;
        }
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    while(1)    {
        cin >> n;
        if(n == 0)  {
            break;
        }
        jain();
    }
}