問題
見た感じ
Nがめちゃくちゃでかくなるので、1手ずつ数えていくのでは間に合わない。
だから、手元で図を描いたりして見ると、おんなじ長さの辺を一気に書いていって、書けなくなったら、次の長さに移っていくという書かれ方をしていて、かつ平行四辺形がたくさん出てくるのに気づいた。
ここから、$n\times m(n>m)$の平行四辺形に注目してその中でできるだけ大きな正三角形をできるだけ多く書くとき、最初の点に戻るとしたらそれまでに
2*(\lfloor n/m\rfloor -1)*m
書き加えているし最初の点に戻らないときは
2*\lfloor n/m\rfloor *m
書きくわえて、$m\times n%m$の平行四辺形に移るを繰り返す。
これを実装すればおk
解法
上の再帰的な操作を繰り返す。
ソースコード
ll n,x;
void Main(){
int y=INF10,z=1;
//入力
cin>>n>>x;
//処理
ll res=0,a,b,c;
a=max(n-x,x);
b=min(x,n-x);
res=n;
while(b!=0){
if(a%b==0){
res+=((a/b)-1)*2*b+b;
}else{
res+=(a/b)*2*b;
}
c=b;
b=a%b;
a=c;
}
//出力
cout << res <<endl;
}
int main(){
cin.tie(nullptr);
cout<<fixed<<setprecision(12);
Main();
}