上海网站设计公司联系方式/网站关键词怎么优化到首页

递归思维题

我们先除去第一条和第二条光线（因为由等边三角形可以得到光线1+光线2等于ab)，剩下的很明显看出是递归。

我们由图看到这需要递归的两条边都是在不断地缩小，而且满足x和y，递归后是y，x % y的关系。 新增加的边数等于2乘以(x - x % y) 的关系。（因为不能整除，所以要先减去多出来的部分。再乘以2）。
还要注意：最后一步时，即x % y == 0时，我们观察一下，由等边三角形的规律，我们发现，增加的边数等于2 * x - y(因为y前面已经算入)。结合参考代码更好理解。

参考代码：

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;ll s;
void dfs(ll x, ll y) {if (x % y == 0) {  // 达到了出口s += x * 2 - y;return;} else {s += (x - x % y) * 2;  // 推理得公式dfs(y, x % y);         // 递归}
}
int main() {ll n, m;scanf("%lld%lld", &n, &m);s = n;n -= m;if (n < m) swap(n, m);dfs(n, m);printf("%lld\n", s);return 0;
}