A game-board consists of N fields placed around a circle. Fields are successively numbered from1 to N clockwise. In some fields there may be obstacles.
Player starts on a field marked with number 1. His goal is to reach a given field marked with number Z. The only way of moving is a clockwise jump of length K. The only restriction is that the fields the player may jump to should not contain any obstacle.
For example, if N = 13, K = 3 and Z = 9, the player can jump across the fields 1, 4, 7, 10, 13, 3, 6 and 9, reaching his goal under condition that none of these fields is occupied by an obstacle.
Your task is to write a program that finds the smallest possible number K.
Player starts on a field marked with number 1. His goal is to reach a given field marked with number Z. The only way of moving is a clockwise jump of length K. The only restriction is that the fields the player may jump to should not contain any obstacle.
For example, if N = 13, K = 3 and Z = 9, the player can jump across the fields 1, 4, 7, 10, 13, 3, 6 and 9, reaching his goal under condition that none of these fields is occupied by an obstacle.
Your task is to write a program that finds the smallest possible number K.
Input
First line of the input consists of integers N, Z and M, 2 <= N <= 1000, 2 <= Z <= N, 0 <= M <= N - 2. N represents number of fields on the game-board and Z is a given goal-field.
Next line consists of M different integers that represent marks of fields having an obstacle. It is confirmed that fields marked 1 and Z do not contain an obstacle.
Next line consists of M different integers that represent marks of fields having an obstacle. It is confirmed that fields marked 1 and Z do not contain an obstacle.
Output
Output a line contains the requested number K described above.
Sample Input
9 7 2 2 3
Sample Output
3
题意：
现在我们要找一个最小的a，使得男主从一号点出发，每次跳a格，中途不遇到障碍，最终走到Z点。
思路：
有方程 1+ax=ny+z。 最小的a需要保证x正整数解，且不存在s<x，使得1+as=ny+障碍的位置。
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int r[1010],n,z,m; void Ex_gcd(int a,int b,int &d,int &x,int &y) { if(b==0){x=1;y=0;d=a;return ;} Ex_gcd(b,a%b,d,y,x); y-=a/b*x; } bool check(int a) { int d,x,y,X; Ex_gcd(a,n,d,X,y); if((z-1)%d!=0) return false; X=(((z-1)/d*X)%(n/d)+n/d)%(n/d); for(int i=1;i<=m;i++){ Ex_gcd(a,n,d,x,y); if((r[i]-1)%d!=0) continue; x=(((r[i]-1)/d*x)%(n/d)+n/d)%(n/d); if(x<=X) return false; } return true; } int main() { while(~scanf("%d%d%d",&n,&z,&m)){ for(int i=1;i<=m;i++) scanf("%d",&r[i]); for(int i=1;i<n;i++) if(check(i)){ printf("%d ",i); break; } } return 0; }