题解 P7679 【[COCI2008-2009#5] JABUKA】

_caiji_ · 2021-07-07 17:38:14 · 题解

设题目中分给每个朋友的苹果数为 x，显然有 x\vert r\land x\vert g，也就是 x\vert \gcd(r,g)。

我们都知道，如果 a\times b=c，那 a 和 b 都是 c 的因数，也就是说因数都是成对出现的（注意特判完全平方数）。

那么，枚举 \gcd(r,g) 的所有因数，可以枚举 i 从 1 到 \sqrt{\gcd(r,g)}，如果 i\vert \gcd(r,g)，说明 i 和 \frac{\gcd(r,g)}{i} 都是 \gcd(r,g) 的因数。这样，我们算法的时间复杂度就只有 O(\sqrt{\gcd(r,g)})，可以轻松通过本题。

下面给出一种代码实现：

#include <cmath>
#include <iostream>
using namespace std;
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int a,b,k,l;//k=gcd(a,b), l=sqrt(k)
int main(){
    cin>>a>>b;
    k=gcd(a,b);
    l=sqrt(k);
    for(int i=1;i<=l;i++){
        if(k%i==0){
            cout<<i<<" "<<a/i<<" "<<b/i<<endl;
        }
    }
    for(int i=l-(l*l==k);i>=1;i--){
    //这里的 l-(l*l==k)，是在特判 k 为完全平方数的情况，如果 k 确实是，那么直接 -1，避免再一次枚举 l 的情况
        if(k%i==0){
            cout<<k/i<<" "<<a/(k/i)<<" "<<b/(k/i)<<endl;
        }
    }
    return 0;
}