社区讨论
全re,样例过了,求调
P5656【模板】二元一次不定方程 (exgcd)参与者 2已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mhjrhf98
- 此快照首次捕获于
- 2025/11/04 07:18 4 个月前
- 此快照最后确认于
- 2025/11/04 07:18 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
#include<bitset>
#define ll long long
#define INF 2147483647
#define P 100000000
using namespace std;
int T;
ll a,b,c,x,y;
ll read()
{
c=getchar();
ll x=0,f=1;
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c-'0');
c=getchar();
}
return x*f;
}
ll exgcd(ll a,ll b)
{
if(b==0)
{
x=1,y=0;
return a;
}
exgcd(b,a%b);
ll t=x;
x=y,y=t-a/b*y;
}
ll gcd(ll a,ll b)
{
if(b==0)return a;
return gcd(b,a%b);
}
int main()
{
T=read();
while(T--)
{
a=read(),b=read(),c=read();
ll d=gcd(a,b);
if(c%d!=0)
{
cout<<"-1"<<endl;
continue;
}
exgcd(a,b);
x=x*c/d,y=y*c/d;
ll tx=b/d,ty=a/d;
ll k=ceil((1.0-x)/tx);
x+=tx*k,y-=ty*k;
if(y<=0)
{
ll ymin=y+ty*ceil((1.0-y)/ty);
printf("%lld%lld\n",x,ymin);
}
else
{
printf("%lld %lld %lld %lld %lld\n",(y-1)/ty+1,x,(y-1)%ty+1,x+(y-1)/ty*tx,y);
}
}
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...