D-日向与乃爱

题意：

已知 n、a、b 和方程 求解出任意非负整数解 x,y ,若无解则输出-1

相关知识：

1. 等价于
2. exgcd(扩展欧几里德算法)
   解不定方程Ax+By=K（得到的x和y只是其中一组解）
   给出A、B、K，求出x和y，满足Ax+By=K

exgcd(a,b,u,v) 的返回值是 gcd(a,b) 且得到的u，v满足au+bv= gcd(a,b)
若k是gcd(a,b)的倍数则有解 x = u ∗ k / d ，y = ( k − a ∗ u ) / b
3. 裴蜀定理
若a,b是整数,且gcd(a,b)=d 那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
ax1+by1=gcd(a,b)
ax2+by2=p*gcd(a,b)

思路：

1. 因为 由相关知识1可得 移向可得ax+by+kn=n-1 ①
2. 由裴蜀定理（相关知识3）可得ax1+by1=gcd(a,b) ② 和 ax2+by2=p*gcd(a,b) ③
   显然p*②的左式=③的左式所以pax1+pby1=ax2+by2
   比较系数得x2=px1 y2=py1
3. 由①的形式我们可以假设③式中的x2,y2是本题答案要求的x,y，所以我们把③带入①中可得p*gcd(a,b)+kn=n-1 ④
4. 由③和④可知我们使用两次exgcd就可得出解，具体过程如下：
   第一次：c=exgcd(a,b,x1,y1) 其中x1,y1满足ax1+by1=gcd(a,b)=c
   则④可划为pc+kn=n-1 ⑤
   第二次：e=exgcd(c,n,u,v) 其中x1,y1满足cu+nv=gcd(c,n)=e ⑥
   假设题目有解则 n-1=tgcd(c,n)=te 把⑥两边同乘以t得*tcu+tnv=n-1 ⑦**
   显然⑤的左式=⑦的左式所以pc+kn=tcu+tnv
   比较系数得p=tu k=tv
5. 综上答案X=x2=tux1 Y=y2=tuy2

注意：两次exgcd所得的x1,y1,u,v可能会是负数要进行归算例如：u=(u%n+n)%n

代码：

#include<bits stdc++.h> 
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &amp;x,ll &amp;y)
{
    if(!b)
    {
        x=1;y=0;
        return a;
    }
    else
    {
        ll tx,ty;
        ll d=exgcd(b,a%b,tx,ty);
        x=ty;y=tx-(a/b)*ty;
        return d;
    }
}
int main()
{
    ll n,a,b;
    scanf("%lld%lld%lld",&amp;n,&amp;a,&amp;b);
    ll x1,y1,u,v;
    ll c=exgcd(a,b,x1,y1);
    ll e=exgcd(c,n,u,v);
    if((n-1)%e) printf("-1\n");
    else{
        ll t=(n-1)/e;
        x1=((x1%n)+n)%n;y1=((y1%n)+n)%n;
        u=((u%n)+n)%n;v=((v%n)+n)%n;
        printf("%lld %lld\n",t*u%n*x1%n,t*u%n*y1%n);
    }
    return 0;
}