SGU 119 Magic Pairs

前提：gcd(N, a0, b0) = 1

• 若 gcd(N, a0) = 1 或 gcd(N, b0) = 1

          若有一個答案(a, b) 不是 (ia0, ib0)，可以找到一個 ia0，使a = ia0

        接著，可以找到一個答案(X, 1)，符合ia0X+ib0 = 1 (mod N)  

        因為b != ib0，那b = kN+b0 (k != 0)，但在mod N的同餘係中，他們是相等的

        故 (ia0, jb0) != (ka0, kb0)(0<= k <= N-1) 是不存在的。

• 若gcd(N, a0) != 1 and gcd(N, b0) != 1

        設 N = a0 * b0 * k ，

        可以找到 (N/a0, 0) 跟 (0, N/b0) 的解，代入後可以發現，(a, b) = (ia0, jb0)

        而又可以發現說，(a, b) = (ia0, ib0) (0 <= i <= N-1)包含了所有的(ia0, ib0+jkb0)

        有必定有一個(x, y)解 = ((k-1)a0, b0)，代入ia0x+(ib0+jkb0)y = 0(mod N)，如果
        有別的(a, b)解，必定要加上kb0，那還是位於(ia0, ib0+jkb0)之中，跳不出來，
        故 (ia0, jb0) != (ka0, kb0)(0<= k <= N-1) 是不存在的。

//By momo
#include<cstdio>
#include<set>
#include<algorithm>
#define MP make_pair
using namespace std;

typedef pair<int, int> PII;
set<PII> che;

int main(){
    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    for(int i = 0; i < n; i++){
        int a = (x*i) % n;
        int b = (y*i) % n;
        che.insert(MP(a, b));
    }
    printf("%d\n", (int)che.size());
    for(set<PII>::iterator it = che.begin(); it != che.end(); it++)
        printf("%d %d\n", it->first, it->second);
}