F Fraction Construction Problem

题意：

给两个数a,b求另外四个数c,d,e,f满足

1. $\frac{c}{d} - \frac{e}{f} = \frac{a}{b}$
2. d < b and f < b
3. $1≤c,e≤4×10^{12}$
   如果不存在就输出-1 -1 -1 -1

思路：

看了题解之后来写一下思路，当时做一个笔记。

这题的关键点在于第二个条件，如果没有第二个条件，这就是一道非常简单的水题因为直接构造 $\frac{a + k}{b} - \frac{k}{b}$(这不是乱杀么 )。

但是有了条件二就无法这样构造，条件二似乎在提示我们， $d * f$一定要是 $b$的整数倍，而且 $d$和 $f$每个都一定要含有 $b$的非1因子，否则无法满足条件二。

那么很自然就会想到质数，当 $b$为质数时上述条件似乎就无法满足了，但是如果分子是质数倍数的话不就又可以直接构造了么？

1. 此时就可以自然地想到，假设分子分母不互质，那么毕竟约分后分母小于原分母，那么约分后的分数就可以随便构造了
   比如：
   约分后是 $\frac{u}{n}$那么就可以构造 $\frac{u + 1}{n} - \frac{1}{n}$(真就乱杀呗 )
2. 那么当分子和分母互质时呢，此时把式子进行通分得 $\frac{cf -ed}{df} = \frac{a}{b}$，根据上面的条件 $d$和 $f$每个都一定要含有 $b$的非1因子,若 $d$与 $f$不互质，那么 $\frac{cf -ed}{df} = \frac{a}{b}$就会约分，那么 $df$一定到达不了 $b$，所以对于存在的质因子数等于1的b一定无解
3. 当 $d$与 $f$互质时 $d*f = b$所以只需要求出 $c$和 $e$满足 $cf-ed=a$这明显就是exgcd的内容了

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define pb push_back
#define eps 1e-8
#define endl '\n'
using namespace std;
const ll maxn = 2e6 + 5;ll t,a,b,c,d,e,f,cb[maxn];
bool vis[maxn];ll exgcd(ll a,ll b, ll &x,ll &y){if(!b){x = 1,y = 0;return a;}else{ll d = exgcd(b,a % b,y,x);y -= a / b * x;return d;}
}void Sz(){for(int i = 2; i <= maxn; i++){if(!vis[i]){vis[i] = 1;for(int j = i + i; j <= maxn; j += i){vis[j] = 1;if(!cb[j]){ll k = i;while(!(j % (k * i))) k *= i;if(k < j)cb[j] = k;}}}}
}void solve(){ll x,y,d = __gcd(a,b);if(d != 1)printf("%lld %lld %lld %lld\n",a / d + 1,b / d,1ll,b / d);else{if(!cb[b])printf("-1 -1 -1 -1\n");else{d = cb[b],f = b / d;exgcd(d,f,x,y);if(x > 0)printf("%lld %lld %lld %lld\n",x * a,f,-y * a,d);elseprintf("%lld %lld %lld %lld\n",y * a,d,-x * a,f);}}
}int main(){Sz();scanf("%lld",&t);while(t--){scanf("%lld %lld",&a,&b);solve();}return 0;
}