AtCoder AGC 046 A - Takahashikun, The Strider (灰色, 200 点)

面白かった。久しぶりの最大公約数ゲー。

• 問題へのリンク

問題概要

平面上に高橋君がおり、真北を向いて立っています。 高橋君が以下の行動を 回繰り返したときに元の位置に戻ってくるような最小の正の整数 を求めてください。

• 今向いている方向に 1 メートル進む。その後、向いている方向を反時計回りに X 度だけ回転させる。

制約

• 

考えたこと

一般には高橋君はグルッと円周をなぞるように動いて、何周かして、スタート地点に戻るようなムーブをします。具体的には

が 360 の倍数

となるような最小の正の整数 を求めればよい、ということになります。

もし が 360 の約数ならば、 が答えとなります。もし と 360 が互いに素ならば、 は 360 の倍数でなければならず、 となります。

一般論として、 と 360 の最大公約数を とします。そして

• 
• 

とします。このとき、 は互いに素となります。そして が の倍数となるような を求めればよいことになります。 は互いに素なので、 が の倍数となります。よって答えは です。

具体的には

となります。

コード

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

long long GCD(long long x, long long y) {
  if (y == 0) return x;
  else return GCD(y, x % y);
}

int main() {
  long long X;
  cin >> X;
  cout << 360 / GCD(X, 360) << endl;
}