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 \((A_0, B_0)\) find all pairs (A, B) such that for any integer X and Y if \(A_0X+B_0Y\) 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, \(A_0\) and \(B_0 (N,A_0,B_0 \le 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.
Example(s)
| Sample Input | Sample Output |
3
1 2
|
3
0 0
1 2
2 1
|
| Author | Resource | Date |
|---|---|---|
| : Michael R. Mirzayanov | : PhTL #1 Training Contests | : Fall 2001 |