首页 > 其他分享 >J - Xingqiu's Joke

J - Xingqiu's Joke

时间:2022-11-05 18:00:32浏览次数:65  
标签:return int Joke ll cin vis ans Xingqiu

传送门

点击查看代码
#include <bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
ll T, a, b;
map<pair<int, int>, int> vis;
vector<int> v;

ll dfs(ll a, ll b)
{
	pair<int, int> p;
	p.first = a, p.second = b;
	if (a == 1 || b == 1)
		return vis[p] = 0;
	if (vis.count(p))
		return vis[p];
	ll ans = a - 1;
	if (b - a == 1)
		return vis[p] = a - 1;
	int cha = b - a;
	for (int i = 0; i < v.size(); ++i)
	{
		if (cha % v[i] == 0)
		{
			int x = a % v[i], y = v[i] - a % v[i];
			ans = min(ans, 1 + x + dfs((a - x) / v[i], (b - x) / v[i]));
			ans = min(ans, 1 + y + dfs((a + y) / v[i], (b + y) / v[i]));
		}
	}
	vis[p] = ans;
	return vis[p];
}

int main()
{
	//IOS; cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--)
	{
		vis.clear(), v.clear();
		cin >> a >> b;
		if (b < a)
			swap(a, b);
		ll cha = b - a;
		for (int i = 2; i <= sqrt(cha); ++i)
		{
			if (cha % i == 0)
			{
				v.push_back(i);
				while (cha % i == 0)
					cha /= i;
			}
		}
		if (cha != 1)
			v.push_back(cha);
		cout << dfs(a, b) << endl;
	}

	return 0;
}

标签:return,int,Joke,ll,cin,vis,ans,Xingqiu
From: https://www.cnblogs.com/jumo-xiao/p/16860739.html

相关文章

  • 大家都学了joke亲传的高数了, 来道练习题吧
    求\[y=\frac{\sqrt{1+x}-\sqrt{1-x}}{\sqrt{1+x}+\sqrt{1-x}}\]的导数口也,不难,只是我至今能同时算出两种不等的答案,算上正解,一共有四种答案了,互不......
  • joke3579说我应该写点东西那我就写
    他告诉我请输入内容。我没法输入内容。一开始打了三个字一个字符:发点颠。然后感觉不太合适就删掉了。joke3579看见了说:你是不是连颠都发不出来了。我说:我死了。他说:......