Как быстро проверить делимость числа?

170

17 ноября 2021, 12:40

Есть 2 числа, нужно найти за короткое время на КАКИЕ числа они оба делятся без остатка? Как это можно сделать? Если пытаться обычным циклом, то получается слишком медленно. Примеру 12 и 6, они оба делятся без остатка на 1, 2, 3, 6.

Answer 1

Сложность алгоритма O(sqrt(n))

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    int gcd = __gcd(a, b);
    vector <int> v;
    for(int i=1; i*i <= gcd; i++) {
        if(gcd % i == 0) {
            if(i*i == gcd) 
                { v.push_back(i); }
            else {
                v.push_back(i);
                v.push_back(gcd/i);
            }
        }
    }
    sort(v.begin(), v.end());
    for(auto el : v)
        cout << el << " ";
    return 0;
}