首页 > 代码库 > CF724C: Ray Tracing
CF724C: Ray Tracing
传送门
CF的题质量真心不低，这道题的标准解法（应该）是exgcd，打比赛的时候想到了具体的推导公式了，也意识到了需要用exgcd，但是因为寝室要锁门了（其实就是太弱，就放弃了。
首先很显然，这条线所经过的总时间应该是$lcm(N,M)$,其实这一点用处不大，但是如果想到了这一点，那么下一步就很好想出来，也就是这整个矩阵的射线轨迹是可以展开在一个$lcm(N,M) \times lcm(N,M)$的矩阵上。到了这一步，只需要把矩形上的每个点铺开在矩阵上然后验证最近的一个点使得在展开的矩阵上横纵坐标相等。
现在问题就转换成了不断的对称一个矩形形成一个正方形，问矩形的每个点在正方形上的坐标。
在进一步就很好看出，对于原矩形上的点$(x,y)$,其在展开的矩形上的对称点应该是$(x \pm (k \times 2 \times N),y \pm (q\times 2\times N))$，
然后需要求的就是最小的$x \pm (k \times 2 \times N)$使得$x \pm (k \times 2 \times N)=y \pm (q\times 2\times N)$
这个就可以用exgcd解决。
也就是用exgcd求$ax+by=c$的问题，简单说一下就是$a=N \times 2$,而且$b=-M \times 2$,$c=\pm x \pm y$，求解这四个方程的最小正整数解。
1 //CF 724C 2 //by Cydiater 3 //2016.10.9 4 #include <iostream> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <map> 9 #include <ctime>10 #include <cmath>11 #include <string>12 #include <cstdio>13 #include <queue>14 #include <map>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(ll i=j;i<=n;i++)18 #define down(i,j,n) for(ll i=j;i>=n;i--)19 inline ll read(){20 char ch=getchar();ll x=0,f=1;21 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}22 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}23 return x*f;24 }25 ll N,M,K,X,Y,ans,oo;26 namespace solution{27 ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}28 void exgcd(ll a,ll b,ll &x,ll &y){29 if(b==0){x=1;y=0;return;}30 exgcd(b,a%b,x,y);31 ll t=x;x=y;y=t-a/b*y;32 }33 void equ(ll a,ll b,ll c,ll &x,ll &y){34 exgcd(a,b,x,y);ll d=gcd(a,b);35 if(c%d!=0){x=oo;return;}36 ll mod=abs(b/d);37 x*=c/d;38 x=((x%mod+mod)%mod+mod)%mod;39 }40 ll get(ll tx,ll ty){41 ll a=(N<<1),b=-(M<<1),c=ty-tx,x,y;42 equ(a,b,c,x,y);43 if(x==oo)return oo;44 ll ans=2*x*N+tx;45 if(ans<0||ans>=oo)return oo;46 return ans;47 }48 void slove(){49 N=read();M=read();K=read();oo=N*M/gcd(N,M)+1;50 up(i,1,K){51 X=read();Y=read();52 ans=oo;53 ans=min(ans,get(X,Y));54 ans=min(ans,get(-X,Y));55 ans=min(ans,get(-X,-Y));56 ans=min(ans,get(X,-Y));57 if(ans==oo)ans=-1;58 printf("%I64d\n",ans);59 }60 }61 }62 int main(){63 //freopen("input.in","r",stdin);64 using namespace solution;65 slove();66 return 0;67 }
CF724C: Ray Tracing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。