Codeforces 74 C. Chessboard Billiard

問題

チェスに新たにビリヤード球という駒を導入する。
この駒はビショップのように動くが、盤の端で（何度でも）跳ね返ることができる。
盤の角で跳ね返った場合、元の進行方向へ戻る。

nxmのチェス盤に、互いに効きのないビリヤード球が最大いくつ置けるか求めよ。

制約条件

2≦n,m≦10^6

方針

盤のどの位置に置いたビリヤード球も、一列目に移動することができる。
なので、一列目にいくつビリヤード球が置けるかのみを考えればよい。

一列目をunion-findとして持っておいて、
(y1,0)場所から出発して、一列目に戻ってきたときの座標を(y2,0)としたとき、
y1とy2をマージする。
これを繰り返した後で、一列目がいくつのunionに分かれているかを見ればよい。

ソースコード

int p[1000000];
int root(int x){
  if(x==p[x])return x;
  return p[x]=root(p[x]);
}
void merge(int a,int b){
  a=root(a); b=root(b);
  if(a!=b)p[a]=b;
}
int n,m;
void run(){
  cin>>n>>m;
  rep(i,n)p[i]=i;
  rep(i,n)rep(dir,2){
    int y=i,x=0,d=dir;
    do{
      int dy,dx;
      if(d==0)dy=0,dx=m-1;
      else if(d==1)dy=n-1,dx=m-1;
      else if(d==2)dy=n-1,dx=0;
      else if(d==3)dy=0,dx=0;
      dy=abs(dy-y); dx=abs(dx-x);
      dy=min(dy,dx);
      y+=d==0||d==3?-dy:dy;
      x+=d==2||d==3?-dy:dy;
      if(y==0||y==n-1)d^=1;
      if(x==0||x==m-1)d=3-d;
    }while(x!=0);
    merge(i,y);
  }
  set<int> s;
  rep(i,n)s.insert(root(i));
  cout<<s.size()<<endl;
}