p119.ans1
======================
3
0 0
1 2
2 1

=================
p119.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, a0, b0;

void read() { cin >> n >> a0 >> b0; }

void solve() {
    // The valid pairs (A, B) are exactly the integer multiples of (A0, B0)
    // taken modulo N: (k*A0 mod N, k*B0 mod N) for k = 0..N-1. Generate all of
    // them, deduplicate, and output sorted by A then B.

    set<pair<int, int>> pairs;
    for(int k = 0; k < n; k++) {
        pairs.insert({(int)((int64_t)k * a0 % n), (int)((int64_t)k * b0 % n)});
    }

    cout << pairs.size() << '\n';
    for(auto& p: pairs) {
        cout << p.first << ' ' << p.second << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p119.in1
======================
3
1 2

=================
p119.py
======================
def find_magic_pairs(N, A0, B0):
    pairs = []

    for k in range(N):
        A = (k * A0) % N
        B = (k * B0) % N
        pairs.append((A, B))

    pairs = list(set(pairs))
    pairs.sort()
    return pairs


def main():
    N = int(input())
    A0, B0 = map(int, input().split())

    pairs = find_magic_pairs(N, A0, B0)

    print(len(pairs))
    for A, B in pairs:
        print(A, B)


if __name__ == "__main__":
    main()

=================
statement.txt
======================
119. Magic Pairs

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


“Prove that for any integer X and Y if 5X+4Y is divided by 23 than 3X+7Y is divided by 23 too.” The task is from city Olympiad in mathematics in Saratov, Russia for schoolchildren of 8-th form. 2001-2002 year.


For given N and pair (A0, B0) find all pairs (A, B) such that for any integer X and Y if A0X+B0Y is divided by N then AX+BY is divided by N too (0<=A,B<N).


Input

Each input consists of positive integer numbers N, A0 and B0 (N,A0,B0£ 10000) separated by whitespaces.


Output

Write number of pairs (A, B) to the first line of output. Write each pair on a single line in order of non-descreasing A (and B in case of equal A). Separate numbers by single space.


Sample Input

3
1 2
Sample Output

3 
0 0
1 2
2 1
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

=================
