Fraction Construction Problem
思路
c
d
−
e
f
=
a
b
\frac{c}{d} - \frac{e}{f} = \frac{a}{b}
dc−fe=ba
a
<
b
&
f
<
b
a < b \& f < b
a<b&f<b
1
≤
1
,
e
≤
4
×
1
0
12
1 \leq 1, e \leq 4 \times10 ^{12}
1≤1,e≤4×1012
当b = 1时，一定无解。
gcd(a, b) != 1，能够较为简单地构造出来。
b
=
p
k
b = p ^ k
b=pk，我们设
d
=
p
k
−
x
,
f
=
p
x
d = p ^{k - x}, f = p ^ x
d=pk−x,f=px，左边方程通分得到
c
p
x
−
e
p
k
−
x
p
k
\frac{c p ^ x - e p ^{k - x}}{p ^ k}
pkcpx−epk−x，则方程
c
p
x
−
e
p
k
−
x
=
a
cp ^ x - ep ^{k - x} = a
cpx−epk−x=a有解，那么一定有
g
c
d
(
p
x
,
p
k
−
x
)
∣
a
gcd(p ^ x, p ^{k - x}) \mid a
gcd(px,pk−x)∣a，
只能
x
=
0
x = 0
x=0,所以
d
=
p
k
=
b
d = p ^ k = b
d=pk=b不符合要求。
所以这时
b
b
b一定有至少两个质因，我们不妨设
d
×
f
=
b
d \times f = b
d×f=b，
d
,
f
d, f
d,f互质，这样我们只要通过拓展欧几里德去求解即可。
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int inf
= 0x3f3f3f3f;
const double eps
= 1e-7;
const int N
= 1e4 + 10;
int prime
[N
], cnt
;
ll c
, d
, e
, f
;
bool st
[N
];
void init() {
for(int i
= 2; i
< N
; i
++) {
if(!st
[i
]) {
prime
[cnt
++] = i
;
}
for(int j
= 0; j
< cnt
&& i
* prime
[j
] < N
; j
++) {
st
[i
* prime
[j
]] = 1;
if(i
% prime
[j
] == 0) break;
}
}
}
bool get_fac(ll n
) {
for(int i
= 0; prime
[i
] * prime
[i
] <= n
; i
++) {
if(n
% prime
[i
] == 0) {
d
= 1;
while(n
% prime
[i
] == 0) {
n
/= prime
[i
];
d
*= prime
[i
];
}
if(n
== 1) return false;
return true;
}
}
return false;
}
ll
exgcd(ll a
, ll b
, ll
& x
, ll
& y
) {
if(!b
) {
x
= 1, y
= 0;
return a
;
}
ll d
= exgcd(b
, a
% b
, x
, y
);
ll temp
= x
;
x
= y
;
y
= temp
- a
/ b
* y
;
return d
;
}
int main() {
int T
;
init();
scanf("%d", &T
);
while(T
--) {
ll a
, b
;
scanf("%lld %lld", &a
, &b
);
int gcd
= __gcd(a
, b
);
if(gcd
!= 1) {
printf("%lld %lld %lld %lld\n", a
/ gcd
+ 1, b
/ gcd
, 1, b
/ gcd
);
continue;
}
if(!get_fac(b
)) {
puts("-1 -1 -1 -1");
continue;
}
f
= b
/ d
;
if(f
< d
) swap(f
, d
);
ll x
, y
;
ll g
= exgcd(f
, d
, x
, y
);
while(y
> 0) x
+= d
, y
-= f
;
printf("%lld %lld %lld %lld\n", x
* a
, d
, -y
* a
, f
);
}
return 0;
}
