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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.