SGU 119.Magic pairs

题意：

对于给出的一个整数N，和一对(A0,B0) 找到所有的整数对(A,B)满足 ： 对于任意 X,Y 当 A0 * X + B0 * Y 能被 N 整除时 A * X + B * Y 也能被 N 整除

---

Solution：

              如果AX+BY能被N整除，则dAX+dBY也能，因A,B<N，所以(dA mod N)X+(dB mod N)Y也能，把所有情况枚举完排序输出

参考代码：

            

#include <stdio.h>

#include <algorithm>

using namespace std;

typedef struct { int a, b; } Set;

Set S[10001];

int N, A, B, cnt;

bool cmp(const Set &x, const Set &y)

{

     return (x.a < y.a || x.a == y.a && x.b < y.b);

}

int main()

{

    scanf("%d %d %d", &N, &A, &B);

    A %= N; B %= N;

    int a = A, b = B;

    do {

       a = (a + A) % N;

       b = (b + B) % N;

       S[cnt].a = a;

       S[cnt].b = b;

       cnt++;

    }  while (a != A || b != B);

    sort(S, S+cnt, cmp);

    printf("%d\n", cnt);

    for (int i = 0; i < cnt; ++i)

        printf("%d %d\n", S[i].a, S[i].b);

    return 0;

}