The problem is from:
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4813
Can someone explain me please what does this code do? why the GCD?
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
int a[100005],b[100005],n,m,s,t;
int gcd(int c,int d)
{
if (d==0) return c;
return gcd(d,c%d);
}
int main()
{
int i,gg;
while (scanf("%d %d",&n,&m)==2&&n+m)
{
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
n--;
if (n)
{
gg=a[1]-a[0];
for (i=1;i<n;i++)
gg=gcd(gg,a[i]-a[i-1]);
}
while (m--)
{
int s,t;
bool ans=true;
scanf("%d %d",&s,&t);
int d=abs(s-t);
if ( (d&1)==1 )
ans=false;
if (n==0&&s+t!=a[0]*2)
ans=false;
d/=2;
if (ans&&n)
{
ans=false;
if (d%gg==0)
ans=true;
if (!ans)
{
int ss;
for (i=0;i<n+1&&!ans;i++)
{
ss=a[i]*2-s;
d=abs(ss-t);
if (d%2==0)
{
d/=2;
if (d%gg==0)
ans=true;
}
}
}
}
if (ans) printf("Y");
else printf("N");
if (m) printf(" ");
}
puts("");
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
