POJ 1061 青蛙的约会（exgcd）

Dear 丶 2023-06-04 13:56 33阅读 0赞

### 嗯... ###

## ##

### 题目链接：http://poj.org/problem?id=1061 ###

两只青蛙相遇时肯定满足：x+k\*m≡y+k\*n(mod L)

x+k\*m-(y+k\*n)=L\*s

k\*(n-m)-s\*L=x-y

即把模线性方程变形后a\*x+b\*y=c，用exgcd求解，

先ax+by=gcd(a,b)

判断c整除g

然后解就是(x+k\*b/g) ,(y-k\*a/g)

注意答案要求非负，所以要进行处理...

### AC代码： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 
     4 using namespace std;
     5 
     6 inline void exgcd(long long a, long long b, long long &g, long long &x, long long &y){
     7     if(!b) { g = a; x = 1; y = 0;}
     8     else { exgcd(b, a % b, g, y, x); y -= x * (a / b);} 
     9 }
    10 
    11 int main(){
    12     long long xx, yy, l, m, n, a, b, c, g, x, y;
    13     scanf("%lld%lld%lld%lld%lld", &xx, &yy, &m, &n, &l);
    14     a = n - m; b = l; c = xx - yy;
    15     exgcd(a, b, g, x, y);//(n-m) * x + l * y = xx - yy 
    16     if(c % g) printf("Impossible\n");
    17     else{
    18         c /= g; b /= g;
    19         printf("%lld\n", (x % b * c % b + b) % b);//处理非负 
    20     }
    21     return 0;
    22 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11482405.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/3c831aa2a8964c2e9c1c39ee9daa9fe7.png

发表评论取消回复

表情：

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

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

相关阅读

相关【exgcd】牛客练习赛 D-青蛙兔子的约会

[D-青蛙兔子的约会\_牛客练习赛111 (nowcoder.com)][D-_111 _nowcoder.com] 题意： ![25d1bbcbb3854cff9e985

梦里梦外;/ 2024年03月22日 12:49/ 0 赞/ 65 阅读

相关 POJ 1061 青蛙的约会（exgcd）

嗯... 题目链接：http://poj.org/problem?id=1061 两只青蛙相遇时肯定满足：x+k\m≡y+k\n(mod L) 　　　

Dear 丶/ 2023年06月04日 13:56/ 0 赞/ 34 阅读

相关青蛙的约会

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

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

相关青蛙的约会 POJ1061

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

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

相关 POJ - 1061 青蛙的约会

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

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

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

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

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

相关青蛙的约会

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

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

相关 poj-青蛙的约会

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

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

相关 POJ - 1061 - 青蛙的约会

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

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

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

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

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