题解：P3421 [POI 2005] SKO-Knights

分析：

我们假设我们现在有两个向量

(2,3)

和

(4,2)

，将他们所能到达的点在几何画板上画出来，再将这些点用红线连起来，在将横坐标相同的点用蓝线连起来便能得到图

1

，就此我们可以发现可以用绿色的两个向量取代之前的两个向量，并且发现有一个向量可以是

(0,B)

的形式。在发现这个之后我们现在的任务便是求出新向量和原向量的关系了，见下边的推导：

所以我们可以将任何两个向量转变成一个在

y

轴的向量和一个其它向量。所以我们只需要不断的将向量转变到

y

轴上使得最终至多一个向量不再

y

轴上就行了。注意在

y

轴上的向量我们可以通过取它们的

\gcd

将它们合并成一个向量。

AC代码：

#include<bits/stdc++.h>//万能头解决一切！！！（勿忘）
using namespace std;
int a[500],b[500];
inline void exgcd(int a,int b,int &x,int &y){
      if(b==0){
          x=1;
          y=0;
          return;
      }
      exgcd(b,a%b,x,y);
      int z=x;
      x=y;
      y=z-(a/b)*y;
      return;
}
int main(){
      int n,m,i,j,k,x,y;
      scanf("%d",&n);
      for(i=1;i<=n;i++){
          scanf("%d%d",&a[i],&b[i]);
      }
      int a1,b1,a2,b2;
      if(!a[1]){
          a1=a[2];
          b1=b[2];
          b2=b[1];
      }else if(!a[2]){
          a1=a[1];
          b1=b[1];
          b2=b[2];
      }else {
        a1=__gcd(a[1],a[2]);
        exgcd(a[1]/a1,a[2]/a1,x,y);
        b1=b[1]*x+b[2]*y;
        b2=abs(b[1]*a[2]-b[2]*a[1])/a1;
      }
      for(i=3;i<=n;i++){
          if(!a1){
            a1=a[i];
            b2=__gcd(b2,b1);
            b1=b[i];
        }else if(!a[i]){
            b2=__gcd(b2,b[i]);
        }else {
            int be=a1,be2=b1;
            a1=__gcd(a1,a[i]);
          exgcd(be/a1,a[i]/a1,x,y);
          b1=b1*x+b[i]*y; 
          b2=__gcd(b2,abs(be2*a[i]-b[i]*be)/a1);
        }
    }
    cout<<a1<<' '<<b1<<endl<<0<<' '<<b2<<endl;
    return 0;
}

题解：P3421 [POI 2005] SKO-Knights

文章操作

分析：

AC代码：

完结撒花！！！希望给各位带来帮助。

相关推荐

评论

题解：P3421 [POI 2005] SKO-Knights