AGC001 B - Mysterious Light
やり直し
B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder
正三角形中の光の経路の長さを求める問題。
解法
f(a, b) := 辺の長さがaとbの平行四辺形の中を光が、2回反射するまでに進む距離とする。
2回反射する時点でまた平行四辺形ができる。
a < bの時、
f(a, b) = f(a, b - a) + 2a
f(a, a) = a
を満たす。
再帰的に計算していけばOKだが辺の長さが≦1012なのでTLEしてしまう。
そこで式を、
a < bの時、
f(a, b) = f(a, b%a) + 2a * (b / a)
b % a == 0の時、
f(a, b) = 2a * (b / a) - a
とすればOK。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; ll f(ll a, ll b) { ll x = min(a, b); ll y = max(a, b); if(y % x == 0) return y / x * x * 2 - x; return 2 * x * (y / x) + f(x, y % x); } int main() { ios::sync_with_stdio(false); cin.tie(0); ll N, X; cin >> N >> X; cout << N + f(X, N - X) << endl; return 0; }