题目来源:https://ac.nowcoder.com/acm/contest/5668/F
题意:c/d-e/f=a/b,这里给出a,b,求可行的c,d,e,f(这里要求d与f值小于b)
解题思路:这是一道数论题,需要一定的数学知识去将这个问题转化为我们熟悉的问题。先通分变为(cf-be)/df=a/b,再假设a1/b1为a/b的最简化的分数。具体验证方法如下: 。
所以问题转化为一个求b的互质因子问题。再一个大的范围内求出第一个被b整除的质数d,然后求f
#include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a , b , sizeof(a)) const int N = 200005; int prime[N],p; bool is_prime[N]; typedef long long ll; void init() { for(int i=2;i<N;++i) { if(!is_prime[i]) prime[++p]=i; for(int j=1;j<=p&&prime[j]*i<N;++j) { is_prime[prime[j]*i]=1; if(i%prime[j]==0) break; } } } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll gcd1(ll a, ll b, ll &x, ll &y) { ll res, t; if(!b) { x = 1; y = 0; return a; } res = gcd1(b, a % b, x, y); t = x; x = y; y = t - (a / b) * y; return res; } ll solve_ex_gcd(ll a, ll b, ll c, ll &x, ll &y) { ll inv = gcd1(a, b, x, y); if(c % inv) { x = -1; y = -1; return -1; } x *= (c / inv); y *= (c / inv); return 0; } void solve() { ll a, b; cin >> a >> b; ll k = gcd(a, b); if(k != 1) { a /= k;b /= k; cout<<a+1<<1<<b<<1<<endl; return ; } if(b == 1 || is_prime[b]==0) puts("-1 -1 -1 -1"); else { ll tmp = 0, time = 0; ll bb = b; for(int i = 1;i <= p && bb != 1; i++) //找两个质因数。 { if(bb % prime[i] == 0) { tmp=prime[i]; while(bb % prime[i] == 0) time++,bb /= prime[i]; break; } } if(bb == 1) {puts("-1 -1 -1 -1");return ;} ll d = 1; for(int i = 1;i <= time; i++) d *= tmp; ll f = bb; ll c = 0, e = 0; solve_ex_gcd(f, d, a, c, e); if(c < 0 && e > 0) cout << e << " " << f << " " << -c << " " << d << endl; else cout << c << " " << d << " " << -e << " " << f << endl; } } int main() { init(); int q; cin>>q; while(q--) solve(); }