【2020年牛客暑假第三场】F题 Fraction Construction Problem

传送门：https://ac.nowcoder.com/acm/contest/5668/F

题意

题目描述 There are t queries. In each query, you are given two positive integers$a$ and $b$$(a, b\leq2×10^6)$ Please print a line consists of four positive integers $c,d,e,f$satisfying the following constraints:

  • $\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$
  • $d < b$ and $f < b$
  • $1\leq c, e \leq4×10^{12}$

If there are multiple solutions, you can print anyone.

If there are no solution, please print “-1 -1 -1 -1” in this line.

输入描述 The first line contains one integer $t$ $(1\leq t\leq 10^5)$ — the number of test cases.

The only line of each test case contains two integers $a$ and $b$$(a, b\leq2×10^6)$

输出描述

For each test case print four integers — $c,d,e,f$. If there are no solution, $c,d,e,f$ should all be $-1$.

输入 $3$ $4$ $1$ $1$ $6$ $37$ $111$

输出 $-1$ $-1$ $-1$ $-1$ $1$ $2$ $1$ $2$ $145$ $87$ $104$ $78$

思路

  • 情况一：$b == 1$和$b$是质数 无解
  • 情况二：$gcd(a,b)!=1$ 假设$k=gcd(a,b)$则存在一组解$(a/k + 1, b/k, 1, b/k)$
  • 情况三：b不是质数 即b可以分成两个相异质因数相乘，所以先找到$d、f$使得$d×f=b$且$d、f$互质 找d，f的方法：先打表3e6以内的素数，然后先找出第一个被b整除的素数，这个数就是d，然后f就是b/d（类似算数基本定理）

在d，f找到之后就开始找c和e了。

已知d*f = b，通分后可得$c×f-e×d=a$（d、f、a都知道，求c、e）,求解c和e，即用扩展欧几里得算法。

注意：求出c和e之后判断一下谁正谁负，毕竟d和f和b的两个相异质因数是不知道对应谁的，可以通过c和e的正负性判断。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x7f7f7f
##define mem(a,b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
// const ll mod = 1e9 + 7;
 const int maxn = 5e6 + 10;
// const double eps = 1e-6;

int prime[1005]; // 素数数组
bool is_prime[maxn]; // is_prime[i]表示i为素数
int p;

void sieve() // 返回n以内的素数个数
{
    int n = maxn;
    mem(is_prime, true);
    is_prime[0] = is_prime[1] = false;
    is_prime[2] = true;

    for(int i = 2;i * i <= n; i++)
    {
        if(is_prime[i])
        {
            prime[++p] = i;
            for(int j = 2 * i;j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
}

ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}

ll ex_gcd(ll a, ll b, ll &x, ll &y)
{
    ll res, t;
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    res = ex_gcd(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 = ex_gcd(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 << " " << b << " " << 1 << " " << b << endl;
        return ;
    }
    if(b == 1  is_prime[b])
        cout << "-1 -1 -1 -1" << endl;
    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)
        {
            cout << "-1 -1 -1 -1" << endl;
            return ;
        }
        ll d = 1;
        for(int i = 1;i <= time; i++)
        {
            d *= tmp; // b的一个因数
        }
        ll f = bb; // b的另一个因数
        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;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
##else
    ios::sync_with_stdio(false);
    sieve();
    int T = 1;
    cin >> T;
    while(T--)
        solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/07/18/2020-nowcoder-shujia-3-f/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！