[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-代码实现

```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; } ``` ## Part4-完结撒花！