AGC 001 B - Mysterious Light

• 問題

問題概要

長さNの正三角形ABCがある.
AB上にあり,AP=Xであるような点からBCと平行に光を放つ.
この光は,辺とそれまで通った点に反射する.
光はどれだけの長さを通るか.
2 <= N <= 10¹²

解法

a * b の平行四辺形に光を放った時の光の長さをf(a,b)とすると,
答えは N + f(X,N-X) であり,
a<b の時, f(a,b) = 2a + f(b-a,a).
ユークリッドの互除法と同じ原理で,
bがaの倍数でない時,
f(a,b) = 2a * floor(b/a) * a + f(b%a,a)
bがaの倍数の時,
f(a,b) = (2a * floor(b/a) -1) * a
となる.

メモ

それっぽいのはできたけどイージーミスでWAが取れなかった.
定式化のスキルが足りない.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;

int main(){
  ll N,X,ans;
  cin >> N >> X;
  ans = N;
  ll a = max(X,N-X);
  ll b = min(X,N-X);
  while(b!=0){
    if(a%b!=0LL) ans += 2*(a/b)*b;
    else ans += (2*(a/b)-1)*b;
    ll a1 = max(a%b,b);
    ll b1 = min(a%b,b);
    a = a1; b = b1;
  }
  cout << ans << endl;
  return 0;
}