博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 1061 青蛙的约会(扩展欧几里得)
阅读量:5827 次
发布时间:2019-06-18

本文共 1173 字,大约阅读时间需要 3 分钟。

思路:设它们跳了t次相遇,那么有 (x+t*m)-(y+t*n) = z*l(z是一个整数,表示它们路程差是l的z倍),变形得

(n-m)*t + z*l = (x-y);

令 a = n-m; b = l; c = x-y;

那么原式变为 a*t + z*b = c;

扩展欧几里得模板,求解形如a*x + b*y = gcd(a,b)方程。

LL extend_gcd(LL a, LL b, LL &x, LL &y){	if(b == 0)	{		x = 1;		y = 0;		return a;	}	LL d = extend_gcd(b,a%b,x,y);	LL t = x;	x = y;	y = t-a/b*y;	return d;}
方程a*x + b*y = c有解的前提是 gcd(a,b) | c,在这个基础上方程有d=gcd(a,b)个不同的解。当中基础解x0 = x'*(c/d)%b(当中x'为a*x'+b*y' = gcd(a,b)的解);通解为xi = x0 + i * (b/d)。

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long#define _LL __int64#define eps 1e-8using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 10;LL extend_gcd(LL a, LL b, LL &x, LL &y){ if(b == 0) { x = 1; y = 0; return a; } LL d = extend_gcd(b,a%b,x,y); LL t = x; x = y; y = t-a/b*y; return d;}int main(){ LL x,y,m,n,l; LL a,b,c,d; while(~scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&l)) { a = n-m; b = l; c = x-y; LL t,z; d = extend_gcd(a,b,t,z); if(c%d != 0) { printf("Impossible\n"); continue; } t = t*(c/d); t = (t%b+b)%b; printf("%lld\n",t); } return 0;}

转载地址:http://vsadx.baihongyu.com/

你可能感兴趣的文章
js 中英文字符串长度
查看>>
让xp系统(win2003系统)支持搜索文件内容
查看>>
Audactiy 和 Sox
查看>>
Apache Rewrite 拟静态配置
查看>>
memcache分布式部署的原理分析
查看>>
动软代码生成器 可用于生成Entity层,可更改模板 /codesmith 也可以
查看>>
LeetCode: Multiply Strings. Java
查看>>
使用Heroku,需要locale至zh_CN,代替zh-CN
查看>>
优步北京B组(8月10日-8月16日奖励规则)
查看>>
eclipse启动tomcat 访问http://localhost:8080 报404错误
查看>>
iOS发展- backBarButtonItem 颜色/文字修改
查看>>
Java生成CSV文件
查看>>
终结者单身——setAccessible(true)
查看>>
IOS应用沙盒文件操作
查看>>
C读取配置文件
查看>>
查找2个分支的共同父节点
查看>>
开源免费跨平台opengl opencv webgl gtk blender, opengl贴图程序
查看>>
enum可以做索引
查看>>
ASP.NET Web API身份验证和授权
查看>>
nginx学习(一):基本安装
查看>>