[noi2002]荒岛野人拓展欧几里得

克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人，一开始依次住在山洞C1,C2,…,CN中，以后每年，第i个野人会沿顺时针向前走Pi个洞住下来。每个野人i有一个寿命值Li，即生存的年数。下面四幅图描述了一个有6个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为1，2，3；每年要走过的洞穴数依次为3，7，2；寿命值依次为4，3，1。

奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？

枚举最小年份，然后判断此年份是否可行；

如何判断可行，只要两个野人有生之年都不会在一个洞里住，那么就可行；

枚举i，j野人，得ci-cj=(pj-pi)*x+ky x表示会相遇的年份；

若无解，说明不会碰到；

否则用ex_gcd求出一个解，然后根据这个解求出x的最小正整数解，与min(l[i]，l[j])比较一下，即可判断；

我犯的主要错误是，算出一个x后，x=x*(c[i]-c[j])/d,x=(x%k+k)%k,这里的k应换成k/d，这是由于x+k*t固然是它的解集，但是由于k和p[j]-p[i]之间还有一些公因数，所以漏掉了一些情况，所以计算之前先将k/d，这样就不会再wa了；

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cstdlib>

 #include<ctime>

 #include<vector>

 #include<algorithm>

 #include<queue>

 #include<map>

 using namespace std;

 #define LL long long

 const int maxn=;

 void gcd(int a,int b,int &d,int &x,int &y){

     if(b==){d=a;x=;y=;return;}

     gcd(b,a%b,d,x,y);

     int t=x;

     x=y;

     y=t-a/b*x;

 }

 int gcd(int a,int b){return b==?a:gcd(b,a%b);}

 int c[maxn],p[maxn],l[maxn],n,Left=;

 void init(){

     cin>>n;

     for(int i=;i<=n;i++){cin>>c[i]>>p[i]>>l[i];Left=max(Left,c[i]);}

     int x,y,d,kl;

     for(int k=Left;k<=;k++){

         bool flag=;

         for(int i=;i<=n;i++)

             for(int j=i+;j<=n;j++){

                 if(flag)break;

                 gcd(p[j]-p[i],k,d,x,y);

                 if((c[i]-c[j])%d)continue;

                 x=x*(c[i]-c[j])/d;

                 kl=k/d;

                 x=(x%kl+kl)%kl;

                 if(x<=l[i]&&x<=l[j])flag=;

             }

         if(!flag){printf("%d\n%d\n",k,clock());return;}

     }

 }

 int main(){

     freopen("1.in","r",stdin);

     freopen("1.out","w",stdout);

     init();

     return ;

 }

其实我更想吐槽把10^6，弄成106的事情，即使一般有经验的人都不会被坑；

巴特西

[noi2002]荒岛野人拓展欧几里得

最新文章

热门文章

巴特西

[noi2002]荒岛野人 拓展欧几里得

最新文章

热门文章

[noi2002]荒岛野人拓展欧几里得