青蛙的约会 POJ1061

╰+攻爆jí腚メ 2022-08-10 14:40 118阅读 0赞

这道题真心坑了我好久，先是扩展欧几里得不清楚，再是写好后交了好多次都是WA，纠结了好久。然后用大数据测了，最后尽然有负数，我惊呆了，怎么找也找不出原因。

最后在网上看了别人的代码，真心觉得自己真.......b明明可以是负的不是吗？你再加上不还是负的吗=\_=

代码如下：

#include<stdio.h>
    #include<cstring>
    #include<stdlib.h>
    #include<iostream>
    __int64 gcd(__int64 x,__int64 y)//求gcd
    {
    	while(y!=0)
    	{
    		__int64 t=x%y;
    		x=y;
    		y=t;
    	}
    	return x;
    }
    void ex_euclid(__int64 a,__int64 b,__int64 &x,__int64 &y)
    {
    	if(b==0)
    	{
    		x=1;y=0;
    		return ;
    	}
    	else  
    	ex_euclid(b,a%b,x,y);
    	__int64 t=x;x=y;y=t-a/b*y;
    }
    int main()
    {
    	__int64 x,y,m,n,l;
    	//freopen("in.txt","r",stdin);
    	//freopen("out1.txt","w",stdout);
    	while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)==5)
    	{
    		__int64 a,b,c,p,q;
    		__int64 g=gcd(n-m,l);
    		if((x-y)%g)printf("Impossible\n");
    		else 
    		{
    			a=(n-m)/g;	b=l/g;	c=(x-y)/g;
    			ex_euclid(a,b,p,q);
    		     __int64 t=-c*p/b;//x=c*p+b*t；令x=0，求出t
                  p=c*p+t*b;
                  if(p<=0)	p+=abs(b);//因为g%l可能是负数，为了保证p为正，再加上b的绝对值（abs函数在stdlib.h里，为整数的绝对值）
                  printf("%I64d\n",p);
    		}
    	}
    		return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读

相关青蛙的约会

青蛙的约会整理：Ackarlix Description 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，

港控/mmm°/ 2022年09月19日 12:27/ 0 赞/ 115 阅读

相关青蛙的约会 POJ1061

这道题真心坑了我好久，先是扩展欧几里得不清楚，再是写好后交了好多次都是WA，纠结了好久。然后用大数据测了，最后尽然有负数，我惊呆了，怎么找也找不出原因。最后在网上看了别人的

╰+攻爆jí腚メ/ 2022年08月10日 14:40/ 0 赞/ 119 阅读

相关 POJ - 1061 青蛙的约会

include <cstdio> using namespace std; define LL __int64 LL x0, y0;

偏执的太偏执、/ 2022年08月07日 09:59/ 0 赞/ 112 阅读

相关 POJ 1061-青蛙的约会（拓展欧几里得）

青蛙的约会 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

绝地灬酷狼/ 2022年07月25日 15:54/ 0 赞/ 97 阅读

相关 poj1061

include<stdio.h> include<math.h> include<iostream> using namespace std;

小鱼儿/ 2022年06月18日 04:19/ 0 赞/ 124 阅读

相关青蛙的约会

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事

Bertha 。/ 2022年06月16日 20:29/ 0 赞/ 144 阅读

相关 poj-青蛙的约会

POJ[ 青蛙的约会 ][Link 1] <table> <tbody> <tr> <td><b>Time Limit:</b> 1000MS</td>

缺乏、安全感/ 2022年06月10日 07:51/ 0 赞/ 139 阅读

相关 POJ - 1061 - 青蛙的约会

首先要知道扩展欧几里得，说白了就是解二元一次方乘，二元一次的话肯定有多解，看题目要求求出最优解。设一共跳了t次 (x + m\t) % l = (y + n\t)

分手后的思念是犯贱/ 2022年06月07日 01:20/ 0 赞/ 138 阅读

相关青蛙的约会POJ1061——同余定理+逆元

青蛙的约会 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 127146 Accepted: 27

àì夳堔傛蜴生んèń/ 2022年05月18日 00:05/ 0 赞/ 149 阅读

相关 poj1061

构造方程 (x + m \ s) - (y + n \ s) = k \ l(k = 0, 1, 2,...) 变形为 (n-m) \ s + k \ l = x - y。即

你的名字/ 2021年12月14日 00:07/ 0 赞/ 152 阅读