POJ1061 扩展欧几里得

简介:

根据题意得出的方程 (m-n)t+Lk=y-x t为步数 k为圈数 然后根据扩展欧几里得就能得出解 然后处理一下就可以了

对L取余要防止负数情况

#include <iostream>
#include<cstdio>

using namespace std;
void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(b==0)
    {
        x=1;y=0;d=a;
        return;
    }
    else
    {
        exgcd(b,a%b,d,x,y);
        long long temp=x;
        x=y;
        y=temp-(a/b)*y;
    }
}
int main()
{
    long long x,y,m,n,l,gcd,ansx,ansy;
    while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l))
    {
        exgcd(m-n,l,gcd,ansx,ansy);
        if((y-x)%gcd==0)
        {
            ansx*=(y-x)/gcd;
            ansx=(ansx%l+l)%l;
            printf("%d\n",ansx);
        }
        else
        printf("Impossible\n");
    }
    return 0;
}


目录
相关文章
|
Java C++
poj 1503 高精度加法
把输入的数加起来,输入0表示结束。 先看我Java代码,用BigINteger类很多东西都不需要考虑,比如前导0什么的,很方便。不过java效率低点,平均用时600ms,C/C++可以0ms过。
43 1
|
6月前
Pseudoprime numbers(POJ-3641 快速幂)
Pseudoprime numbers(POJ-3641 快速幂)
poj 1185 炮兵阵地 (状态压缩dp)
如果你是刚刚开始做状态压缩dp,我建议你先看看 poj 3254 Corn Fields 这是一道比这一题更简单,更容易入门的题目。 还有在代码中我用了一个很巧妙的方法求一个数二进制数中1的个数 具体请看我博客中 x& (x - 1)==0 这篇文章 链接 。
39 1
POJ-3641,Pseudoprime numbers(快速幂)
POJ-3641,Pseudoprime numbers(快速幂)
poj-2909-哥德巴赫猜想
Description For any even number n greater than or equal to 4, there exists at least one pair of prime numbers p1 and p2 such that n = p1 + p2 This conjecture has not been proved nor refused yet.
797 0
|
机器学习/深度学习
【OJ】贪心法 Saruman&#39;s Army POJ 3069 /acmclub 12132
题目链接:点击打开链接 /* 6 10 贪心法Saruman's Army POJ 3069 1 7 15 20 30 50 ans=3 */ #include #include using namespace std; int x[1010]; int main(){ // freopen("贪心法 Saruman's Army poj3069.
844 0