[P13016]最大因数-题解

Part0-前言(可略过)

这道题我在GESP赛场上打了好久才过，~~but总分100~~

Part1-思路

我来提供一种数论的方法 ~~(我作为一个13岁初中生自然没学过LCA)~~
0.不妨设小的数为

a

，大的数为

b

，计数器为

m

；
1.将这两个数排序(并更新

a

，

b

编号)，其中大的那个找一下它的父亲(因为它的父亲的数肯定比他小)，并将数更新为它的父亲，将

m

加1；
2.它的父亲的找法：设

i

，从2开始遍历直到

\sqrt{b}

，如果

b

能被

i

整除的话，它的父亲就是

b/i

；
3.输出

m

。(别忘了有多组样例)

Part2-举个例子

例如，4和16：
第一步，4<16，将16更新为8，

m

=1；
第二步，4<8，将8更新为4，

m

=2；
第三步，4=4，直接输出

m

，即2。

Part3-代码实现

{\color{22dd22} AC }

code(C++):

CPP

#include<bits/stdc++.h>
using namespace std;
long long e(int x) //求父亲
{
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			return x/i;
		}
	}
	return 1;
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int a,b,m=0;
		cin>>a>>b;
		while(a!=b)
		{
			if(a>b)
			{
				swap(a,b);
			}
			b=e(b);
			m++;
		}
		cout<<m<<endl;
	}
	return 0;
}

[P13016]最大因数-题解

文章操作

Part0-前言(可略过)

Part1-思路

Part2-举个例子

Part3-代码实现

Part4-完结撒花！

相关推荐

评论

[P13016]最大因数-题解