Uva - 10407 - Simple division

Problem  Link : https://uva.onlinejudge.org/external/104/10407.pdf

Idea : Actually, we have to find out the largest value of the divisor which makes same remainder for every number.Gcd always gives same remainder which is zero but it is not the biggest divisor.Say, 2,8,14 here ,gcd is 2.and the number 3 also gives same remainder for each number which is 2. Here, we use congruence formula.

     a _=b(mod d)

is same as

   a-b _=0(mod d)

So, by finding the gcd of difference for each number is the solution.



Code First Then see Solution

Code :

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        vector <int> v,v1;
        if(n==0)
            break;
        v.push_back(n);
            int m;
        while(true)
        {
            cin>>m;
            if(m==0)
                break;
            v.push_back(m);
        }
        for(int i=1;i<v.size();i++)
            v1.push_back(abs(v[i]-v[i-1]));
        sort(v1.begin(),v1.end());
        int gcd=v1[0];
        for(int i=1;i<v1.size();i++)
            gcd=__gcd(gcd,v1[i]);
        cout<<gcd<<endl;
    }
    return 0;
}