codeforces-724c-Ray Tracing-扩展欧几里得

题目链接

题意：给你一个n*m的矩形，一束激光从（0，0）点发出，沿（1，1）方向，遇到边界会折90度角反射，已知激光的速度为根号2。给你K个点，问你最早经过该点的时间，如果不会经过该点，输出-1.

思路：哎……做了这么多数论，一开始还是看不出来这是数论。网上有暴力模拟每个边界上的反射点的做法，不过这么暴力的做法明显不适合我……
不会的题目先打个表，以34的矩形为例，打个表就可以发现经过的点有这么个规律：
x:123210123210
y:123432101234
经过的点的横纵坐标是连续的1~n~0与1~m~0，直到到达端点，可以很简单的想出最多是走nm/gcd(n*m)步。
我们以2n与2m为一个周期，那么给出的坐标一定可以写成(2kn+x,2tm+y)，所以可以列出方程2kn±x=2tm±y,用扩展欧几里得求出最小的正整数k与m，最后的2kn±x就是所求时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long INF=0x3f3f3f3f3f3f3f; 
long long gcd(long long a,long long b)
{
	if(b==0)return a;
	 else return gcd(b,a%b);
}
long long exgcd(long long a, long long b, long long &x, long long &y)
{  
    if (!b) {x = 1; y = 0; return a;}  
    long long d = exgcd(b, a % b, y, x);  
    y -= a / b * x;  
    return d;  
}   
 
 
int fangcheng(long long a,long long b,long long c,long long &x,long long &y)
{
    long long d=exgcd(a,b,x,y);
    if(c%d)
        return -1;
    int k=c/d;
    x*=k; y*=k;
	long long t=b/d;
	if(t<0)t=-t;
	x=(x%t+t)%t;
	y=(c-(x*a))/b;
	//printf("fangcheng : a=%lld,b=%lld,c=%lld jiex:%lld jiey:%lld\n",a,b,c,x,y);   
    return 1;
} 
int main()
{
	int i,j,k;
	long long n,m;
	long long xx,yy,x,y;
	scanf("%lld%lld%d",&n,&m,&k);
	while(k--)
	{
		scanf("%lld%lld",&x,&y);
		long long ans=INF;
	    int flag=fangcheng(2*n,-2*m,x+y,xx,yy);
	    if(flag==1 && 2*n*xx-x>=0)ans=min(ans,2*n*xx-x);
	    flag=fangcheng(2*n,-2*m,-x+y,xx,yy);
	    if(flag==1 && 2*n*xx+x>=0)ans=min(ans,2*n*xx+x);
	    flag=fangcheng(2*n,-2*m,x-y,xx,yy);
	    if(flag==1 && 2*n*xx-x>=0)ans=min(ans,2*n*xx-x);
	    flag=fangcheng(2*n,-2*m,-x-y,xx,yy);
	    if(flag==1 && 2*n*xx+x>=0)ans=min(ans,2*n*xx+x);
	    if(ans>m*n)printf("-1\n");
	     else printf("%lld\n",ans);
	}
	return 0;
}