约数

⬅ 返回

1、试除法求约数

#include <iostream>
#include <queue>
using namespace std;
 
int main(){
    
    int n;cin>>n;
    while(n--)
    {
        priority_queue<int,vector<int>,greater<int>>pq;
        
        int x;
        cin>>x;
        for(int i=1;i<=x/i;i++)
        {
            if(x%i==0){
		            pq.push(i);
            
                if(i!=x/i)pq.push(x/i);
                
            }
        }
        while(pq.size())
        {
            auto t = pq.top();
            cout<<t<<" ";
            pq.pop();
        }
        cout<<endl;
    }
}

2、最大公约数（辗转相除法）

2.1、思路

2.2、代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int a, b;
        cin >> a >> b;
        //辗转相除，直到小括号内右边数为0
        while(b)
        {
            //c 一定小于 b
            int c = a % b;
            //小括号左边放除数，右边放约数
            a = b;
            b = c;
        }
        //小括号内左边数为最大公约数
        cout << a << endl;
    }
}

2.3、库函数__gcd(a,b)优化

原理

#include<iostream>
#include<algorithm>//__gcd(a,b)函数求解a与b的最大公约数
using namespace std;
 
int main(){
    
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<__gcd(a,b)<<endl;
    }
}