[Jzoj] 3793. 数字对

题目描述

对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。 给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。

题目解析

给定$（a,b）$，将其还原 唯一还原方法 若 $a>b$，则$（a,b）->(a-b,b)$ 若 $b>=a$，则$（a,b)->(a,b-a)$ 对于给定的$n$，枚举所有的$i$，模拟还原$（n,i）$ 取其中最少步数为解

类比求$gcd$的辗转相除法 若 $a>b$，则$（a,b）->(a$%$b,b)$ 若 $b>=a$，则$（a,b)->(a,b$%$a)$

代码

#include<bits/stdc++.h> #define ll long long using namespace std; ll n,ans=1e9; ll dfs(ll l,ll r) { if(r==1) return l-1; if(!r) return 1e9; return l/r+dfs(r,l%r); } int main() { cin>>n; for(ll i=1;i<n;i++) ans=min(ans,dfs(n,i)); cout<<ans; }