119. Magic Pairs
time limit per test: 0.5 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
//started 22:24
//read error 1 23:15
//read answer 0:41 晕,既然a0x+b0y|n,ax+by|k*n,直接乘上k再modn即可....
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int extgcd(int a,int b,int &x,int &y){
int d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}
else {
x=1;y=0;
}
return d;
}
typedef pair<int ,int> P;
P heap[10001];
int cnt;
int main(){
int n,a0,b0;
scanf("%d%d%d",&n,&a0,&b0);
int ty,tx,tmp1,tmp2;
int abgcd=extgcd(a0,b0,tx,ty);
int nabgcd=extgcd(abgcd,n,tmp1,tmp2);
n=n/nabgcd;
a0=a0/nabgcd;
b0=b0/nabgcd;
for(int i=0;i<n;i++){
int a=a0*i%n;
int b=b0*i%n;
heap[i]=P(a,b);
}
sort(heap,heap+n);
printf("%d\n",n);//必然有n个解
for(int i=0;i<n;i++){
printf("%d %d\n",heap[i].first*nabgcd,heap[i].second*nabgcd);
}
return 0;
}