Проверка делимости — разбор задачи

1. Идея

Для каждого запроса даны два целых числа n и d. Нужно понять, существует ли целое число k, для которого выполняется равенство n = d * k.

Это и есть обычная проверка делимости:

• если d != 0, то нужно проверить, что n % d == 0;
• если d == 0, то деление и остаток использовать нельзя, поэтому случай нужно обработать отдельно.

По условию, при d = 0 ответ YES только тогда, когда n = 0.

2. Наблюдения

Наблюдение 1

Если d != 0, то число n делится на d нацело тогда и только тогда, когда остаток от деления равен нулю.

То есть:

• n % d == 0 → ответ YES;
• иначе → NO.

Наблюдение 2

Случай d = 0 особый.

По условию запрос считается успешным только если n = 0, потому что равенство n = 0 * k возможно только для n = 0.

Значит:

• n = 0, d = 0 → YES;
• n != 0, d = 0 → NO.

Наблюдение 3

Каждый запрос независим от остальных, значит можно просто обработать их по одному.

3. Алгоритм

Для каждого из q запросов:

1. Считать n и d.
2. Если d == 0:
   • если n == 0, вывести YES;
   • иначе вывести NO.
3. Иначе:
   • если n % d == 0, вывести YES;
   • иначе вывести NO.

4. Почему это работает

Рассмотрим все возможные случаи.

Случай 1: d != 0

По определению делимости число n делится на d, если существует целое k, такое что n = d * k.

Это эквивалентно тому, что остаток от деления n на d равен нулю. Значит проверка n % d == 0 точно дает правильный ответ.

Случай 2: d == 0

Обычное деление на ноль не определено, поэтому проверять остаток нельзя. Но в условии отдельно сказано, что запрос считается успешным только при n = 0.

Значит:

• если n = 0, ответ YES;
• если n != 0, ответ NO.

Других случаев нет, поэтому алгоритм полностью покрывает задачу и всегда работает корректно.

5. Сложность

На один запрос выполняется константное число операций, то есть O(1).

Для всех q запросов:

• время: O(q);
• дополнительная память: O(1).

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        long long n, d;
        cin >> n >> d;

        if (d == 0) {
            if (n == 0) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        } else {
            if (n % d == 0) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }

    return 0;
}

7. Код на Python 3

q = int(input())

for _ in range(q):
    n, d = map(int, input().split())

    if d == 0:
        if n == 0:
            print("YES")
        else:
            print("NO")
    else:
        if n % d == 0:
            print("YES")
        else:
            print("NO")