本文主要是介绍poj 1061 数论 扩展欧几里得算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目还算简单,但是得用long long
#include<cstdio>
#define size_num 51000
#include<cstring>
#include<iostream>
using namespace std;
void exgcd(long long a,long long b,long long &d,long long &x,long long& y)
{if(!b){d=a;x=1;y=0;}else{exgcd(b,a%b,d,x,y);int temp=x;x=y;y=temp-x*(a/b);}
}
int deal()
{long long x,y,m,n,L;cin>>x>>y>>m>>n>>L;long long ad,ax,ay;exgcd(n-m,L,ad,ax,ay);long long ans=(ax*(x-y))/ad;long long bb=L/ad;ans=(ans%bb+bb)%bb;if((y-x)%ad!=0)cout<<"Impossible\n";elsecout<<ans<<endl;return 0;
}
int main()
{while(deal());return 0;
}
这篇关于poj 1061 数论 扩展欧几里得算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!