自动搬运

查看原文

来自洛谷，原作者为

	清小秋ovo AFO

搬运于2025-08-24 22:32:08，当前版本为作者最后更新于2021-08-16 12:35:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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$ 是 $k$ 的因数，$j$ 是 $m,n$ 的因数。

因为 $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$ 的值，并存入一个容器中。

注意这里存值的时候需要特判是否为一个完全平方数，如果是的话就不进行存入了，不然会输出重复。

在第一遍循环完成后，倒序输出容器中的每一个数，以保证最终的结果是升序排列的。

代码

返回最大公因数的函数

int gcd(int a,int b) {  return b > 0 ? gcd(b, a%b) : a;  } 

第一个循环，求出前半部分的因数，并存入后续的因数

//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);
       }
   }

倒序输出

for(int i=num.size()-1;i>=0;i--){
       cout<<num[i]<<" "<<a/num[i]<<" "<<b/num[i]<<endl;
   }

完整代码

#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;
  }
}

菜鸡一个，有写的不好的地方请多多包涵。