B - Mysterious Light AtCoder Grand Contest 001
問題概略
制約
- と はいずれも整数である。
解法
この問題が難しいのは、残された形が三角形、台形、平行四辺形と変化していくから。
一回の操作を平行四辺形を小さい平行四辺形に変えるものだと考えれば、ユークリッドの互除法的な操作をすることで解ける。
解法
public static void main(String[] args)
{
//longを忘れるなオーバーフローするぞ
N = sc.nextLong();
long x = sc.nextLong();
long res = N;
long a = N - x;
long b = x;
if (a < b)
{
long c = a;
a = b;
b = c;
}
while (b > 0)
{
res += (2 * (a / b)) * b;
long c = a % b;
a = b;
b = c;
}
System.out.println(res);
}