POJ 1061 青蛙的约会 扩展欧几里得
2018-06-17 23:43:25来源:未知 阅读 ()
扩展欧几里得模板套一下就A了,不过要注意刚好整除的时候,代码中有注释
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; typedef long long ll; ll exgcd(ll a, ll b, ll&x, ll&y) { if (b == 0) { x = 1; y = 0; return a; } ll r = exgcd(b, a%b, y, x); ll t = x; y = y - a/b*t; return r; } bool modular_linear_equation(ll a, ll b, ll n) { ll x, y, x0, i; ll d = exgcd(a, n, x, y); if (b%d) { printf("Impossible\n"); return false; } x0 = x*(b/d)%n; //x0为方程的一个特解,可以为正也可以为负。题目要求的是最小的非负数 ll ans; if(x0<0) { ans=x0; for(i = 0;ans<0; i++) ans=(x0 + i*(n/d))%n; } else if(x0>0) { ans=x0; ll temp; for(i=0;ans>=0;i++) { temp=ans; ans=(x0 - i*(n/d))%n; } ans=temp; } else ans=n; //此时x0=0,但是结果一定会大于0,所以要加一个n printf("%I64d\n",ans); return true; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ll x,y,m,n,L; while(~scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L)) { ll temp1=m-n,temp2=y-x; if(temp1<0) { temp1=-1*temp1; temp2=-1*temp2; } modular_linear_equation(temp1,temp2,L); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash