首页 > 其他分享 >荒岛野人Savage

荒岛野人Savage

时间:2024-03-28 15:58:12浏览次数:21  
标签:Savage 正整数 gcd 荒岛 野人 b1 y1 ax x1

题目描述

image

image

样例

3
1 3 4
2 7 3
3 2 1
6

分析

首先,我们先设4个变量,初始坐标d[i],每年步数p[i],寿命l[i],根据题目很容易得到一个不等式

(假设i,j是两个野人的标号,x为经过的年数):(d[i] + p[i] * x) % m != (d[j] + p[j] * x) % m 。

解不等式。。。不会,但可以转化一下,把不等式转为等式(d[i] + p[i] * x) % m = (d[j] + p[j] * x) % m,使等式无解,

无解条件就是解得的x的最小,正整数解比两个野人的其中一个的寿命要大即可。

但这个等式用代码解就需要转换一下,假设(d[i] + p[i] * x) % m = (d[j] + p[j] * x) % m = t,

(d[i] + p[i] * x) = m * y1+t,(d[j] + p[j] * x) = m * y2+t。

那么等式就可以化为:d[i] + p[i] * x - m * y1 = d[j] + p[j] * x - m * y2;

即为: d[i] - d[j] = (p[i] - p[j]) * x + m * (y1 - y2)。这就转化成了 ax+by=c 的形式,

可以用扩展欧几里得定理做,这里的y对答案无贡献,可忽略, 接下来就是用公式求最小正整数解了。

补如何求ax + by = c的最小正整数解

对于 ax + by = c的方程, 先用扩展欧几里得解出方程 ax + by = gcd(a,b)的一组解 (x,y),

接着判断 c % gcd(a,b) 是否等于0,如果不等于则方程无解

然后假设b1 = b / gcd(a,b),x1 = (x + b1) * (c / gcd(a,b) );

那么方程的最小正整数解为x1 = (x1 % b1 + b1) % b1,y1 = (c - a * x1) / b;

solution

#include<bits/stdc++.h>
const int maxn=1<<5;
const int inf=0x7f7f7f7f;
using namespace std;
int n,r,m,q,x,y,a,b,t,d[maxn],p[maxn],l[maxn];

int exgcd(int a,int b,int &x,int &y) {	//解方程模板 
    if (b==0) {
        x=1;
        y=0;
        return a;
    }
    int ret=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return ret;
}

bool check(int z)
{
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)		//枚举没两个野人,看是否符合方程 
		{
			a=p[i]-p[j];
			b=d[j]-d[i];
			m=z;
			x=0,y=0;
			int q=exgcd(a,m,x,y);	//gcd(a,b) 
			if(b%q)continue;		//无解 
			b/=q;					// b此时等价于c/gcd(a,b); 
			m/=q;					//等价于上面的b1
			if(m<0)m=-m;			//不确定正负 
			t=(x+m)*b;
			t=(t%m+m)%m;			//最小正整数解公式 
			if(t<=l[i]&&t<=l[j]) return 0;		//方程无解 
		}
	}
	return 1;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&d[i],&p[i],&l[i]),r=max(r,d[i]);
	for(int i=r;i<=1e6;i++)			//枚举到极限数据,找到最小的就输出 
	{
		if(check(i))
		{
			printf("%d\n",i);
			return 0;
		}
	}
	
	return 0;
}

标签:Savage,正整数,gcd,荒岛,野人,b1,y1,ax,x1
From: https://www.cnblogs.com/oceansofstars/p/18101890

相关文章

  • P2421-荒岛野人Savage题解
    好久没写题解了啊洛谷P2421荒岛野人题目大意:有一个有很多洞的岛上,住了\(n\)个野人,每个野人的初始位置为\(c[i]\),换洞的速度为\(p[i]\),寿命为\(l[i]\)。要求求出洞的最少个数\(M\)满足每个野人在生存状态下不会在同一年和其他野人住在同一个山洞里。概括版:很多个青蛙的约会。......
  • 森林之子野人怎么吃 怎么烤肉_森林2森林之子攻略
    咦,在这圣索弗朗代兰县的丛林当今世界,想活留下来要是懂冒险。《丛林之母》格斗游戏中,他们要直面雪人的突袭,也要补足食材,因此间接杀掉雪人当郊游也是极好的优先选择。所以丛林之母呢吃雪人呢?丛林之母雪人呢吃:在《丛林之母》中,玩者在击破雪人后能吃雪人来补足食材,但是无法间接吃遗......
  • AI传教士和野人渡河问题-实验报告
    一题目要求:       设有m个传教士和n个野人来到河边,打算乘一只船从左岸渡到右岸去,该船每次最多载3人。在任何时候,如果野人人数超过传教士人数,那么野人就会把传教士吃......
  • AI A_star算法野人渡河-实验报告
    1、问题描述及实验要求       请用A*算法实现野人过河问题,(1)分析设计估价函数f(2)采用C语言或Python编程实现(代码中适当加注释,输出具有可读性)。       问题描......
  • [NOI2002] 荒岛野人
    exgcd简单题首先容易想到先枚举m,然后判断。至于判断只需用联立方程,先给ci-1\(c_i+p_i\timest\equivx\pmodm\)\(c_j+p_j\timest\equivx\pmodm\)即\(......