P7679
清小秋ovo
·
·
题解
P7679 题解
这个题的题意其实非常明了，只需要枚举出 a 和 b 的所有公因数即可。
当我看到这个题的思路如此简单时，就立马跑到下面看了一眼数据范围。
这题果然不简单。
题意解析
这里就不做过多赘述了，说白了就是找出两个数的所有公因数，因为这样才能满足同时平均分配的要求。
那么这个题的问题其实可以转化为：
如何快速枚举出两数的所有公因数并将其升序输出？
解题思路
第一步，我们需要找出两个数字的最大公因数:
\gcd(a,b)
这个数字便是我们需要枚举的最大范围。
可是这样的优化是远远不够的。
但是我们只要能够证明出，两数的所有公因数，一定是 \gcd(a,b) 的因数，那么代码的速度就可以极大的被提升。
该如何证明呢？
设两数分别为 a 和 b，k=\gcd(a,b)。
则有：
a=k\times m
b=k\times n
不难看出，m 与 n 互质。
设 x 为 a 和 b 的任意一个公约数，则：
a=p\times x
b=q\times x
若 x 不是 k 的因子，则：
a=k\times m=p\times i\times j=p\times x
b=k\times n=q\times i\times j=q\times x
因为 $i<x$，所以 $j>1$。
这样就导致 $m,n$ 的公因数 $>1$， 与 $m,n$ 互质的特性矛盾。
这样就成功证明，两个正整数的公因数一定是它们最大公因数的因数。
在确定完这一特征之后，我们就可以进一步优化算法，将原来的枚举范围缩减到：
$$\sqrt {\gcd(a,b)}$$
或者：
$$\sqrt k$$
因为如果我们确定了一个数 $i$ 是 $k$ 的因数，那么我们就自动的找出了 $k$ 的另外一个因数，也就是 $\frac k i$。
所以在第一遍循环时，一边找到从 $1$ 至 $\sqrt k$ 的所有因数，并且对于每个因数，同时记录下 $\frac k i$ 的值，并存入一个容器中。
注意这里存值的时候需要特判是否为一个完全平方数，如果是的话就不进行存入了，不然会输出重复。
在第一遍循环完成后，**倒序**输出容器中的每一个数，以保证最终的结果是升序排列的。
## 代码
返回最大公因数的函数
```cpp
int gcd(int a,int b) { return b > 0 ? gcd(b, a%b) : a; }
```
第一个循环，求出前半部分的因数，并存入后续的因数
```cpp
//n为sqrt(k), k为gcd(a,b)
for(int i=1;i<=n;i++){
if(k%i==0){
cout<<i<<" "<<a/i<<" "<<b/i<<endl;
//注意这里需要特判
if(i*i!=k) num.PB(k/i);
}
}
```
倒序输出
```cpp
for(int i=num.size()-1;i>=0;i--){
cout<<num[i]<<" "<<a/num[i]<<" "<<b/num[i]<<endl;
}
```
## 完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define PB push_back
//最大公因数
int gcd(int a,int b) { return b > 0 ? gcd(b, a%b) : a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int a,b;
vi num;
cin>>a>>b;
int k = gcd(a,b);
int n=int(sqrt(gcd(a,b)));
for(int i=1;i<=n;i++){
if(k%i==0){
cout<<i<<" "<<a/i<<" "<<b/i<<endl;
if(i*i!=k) num.PB(k/i);
}
}
for(int i=num.size()-1;i>=0;i--){
cout<<num[i]<<" "<<a/num[i]<<" "<<b/num[i]<<endl;
}
}
```
菜鸡一个，有写的不好的地方请多多包涵。