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

posted on 2021-07-07 17:38:14 | under 题解 | source

设题目中分给每个朋友的苹果数为 \(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;
}