Как найти НОД на отрезке?

Question

Возможно вопрос глупый, но как НОД запихнуть в определенный отрезок? К своему сожалению, я могу найти просто НОД, а не то что нужно. Поэтому моя программа работать не будет. (я это понимаю, просто показываю какая программа есть)

#include <iostream> 

using namespace std;

int nod(int a, int b)
{
    while (a && b)
        a > b ? a %= b : b %= a;
    return a | b;
}

int main() 
{ 
    int a, b, n, low, high;
    cin >> a >> b;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> low >> high;
        if (low <= nod(a, b) <= high)
            cout << nod(a, b) << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

объясните пожалуйста.

Answer 1

#include <bits/stdc++.h>
    
using namespace std;

int getGreaterDivisor(vector <int> divisorsA, vector <int> divisorsB, int left, int right) {
    for (int i = divisorsA.size() - 1; i >= 0; --i) {
        if (binary_search(divisorsB.begin(), divisorsB.end(), divisorsA[i]) && divisorsA[i] >= left && divisorsA[i] <= right) {
            return divisorsA[i];
        }
    }
    return -1;
}

vector<int> getDivisors(int number) {
    vector <int> divisors;

    for (int i = 1; i * i <= number; ++i) {
        if (number % i == 0) {
            divisors.push_back(number / i);
            if (number / i != number / (number / i)) {
                divisors.push_back(number / (number / i));
            }
        }
    }

    sort(divisors.begin(), divisors.end());

    return divisors;
}

int main() {
    int a, b, n;

    cin >> a >> b;
    if (a > b) 
        swap(a, b);

    cin >> n;

    for (int i = 0; i < n; ++i) {
        int left, right;
        cin >> left >> right;

        vector <int> divisorsA = getDivisors(a);
        vector <int> divisorsB = getDivisors(b);
        
        int result = getGreaterDivisor(divisorsA, divisorsB, left, right);
        cout << result << "\n";
    }

    return 0;
}

Answer 2

gcd можно найти с помощью библиотечной функции https://en.cppreference.com/w/cpp/numeric/gcd.

Для более двух аргументов можно воспользоваться свойством с вики:

If none of a1, a2, . . . , ar is zero, then gcd( a1, a2, . . . , ar ) = gcd( gcd( a1, a2, . . . , ar-1 ), ar ).

БЛОГ НА HUSL

Как найти НОД на отрезке?

Ответы (2 шт):