lightoj1215

maksyuki 发表于 oj 分类，标签: 数论-素因子分解

27 8月 2015

1215 - Finding LCM

You will be given a, b and L. You have to find c such that LCM (a, b, c) = L. If there are several solutions, print the one where c is as small as possible. If there is no solution, report so.LCM is an abbreviation used for Least Common Multiple in Mathematics. We say LCM (a, b, c) = L if and only if L is the least integer which is divisible by a, b and c.

Input

Input starts with an integer T (≤ 325), denoting the number of test cases.

Each case starts with a line containing three integers a b L (1 ≤ a, b ≤ 10⁶, 1 ≤ L ≤ 10¹²).

Output

For each case, print the case number and the minimum possible value of c. If no solution is found, print 'impossible'.

Sample Input	Output for Sample Input
33 5 30209475 6992 770868002 6 10	Case 1: 2Case 2: 1Case 3: impossible

题目类型：素因子分解

算法分析：这是一道使用素因子分解求解LCM相关问题的典型例题。首先将a、b和L进行素因子分解，然后从小到大枚举判断L的每个素因子的指数值k，若a和b对应的指数值的最大值小于k，则c的对应的指数值就是k。若a和b对应的指数值的最大值等于k，则不需要进行任何操作。若大于k，则不可能出现这种情况，直接输出”impossible”即可。枚举完L的所有素因子之后，注意要查看此时a和b是否还有没在前面判断中出现的素因子。若还有，则也输出”impossible”。反之，则输出c的值

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

LL aa[maxn], bb[maxn], cc[maxn], lena, lenb, lenc;
LL maxval, cnta, cntb;

LL PP (LL vala, LL valb, LL valL)
{
    lena = lenb = lenc = 0;
    memset (aa, 0, sizeof (aa));
    memset (bb, 0, sizeof (bb));
    memset  (cc, 0, sizeof (cc));
    cnta = cntb = 0;

    for (LL i = 2; i * i <= vala; i++)
    {
        if (vala % i == 0)
        {
            cnta++;
            while (vala % i == 0)
            {
                aa[i]++;
                vala /= i;
            }
        }
    }
    if (vala > 1)
    {
        aa[vala]++;
        cnta++;
    }

    for (LL i = 2; i * i <= valb; i++)
    {
        if (valb % i == 0)
        {
            cntb++;
            while (valb % i == 0)
            {
                bb[i]++;
                valb /= i;
            }
        }
    }
    if (valb > 1)
    {
        bb[valb]++;
        cntb++;
    }

    maxval = -INF;
    for (LL i = 2; i * i <= valL; i++)
    {
        if (valL % i == 0)
        {
            while(valL % i == 0)
            {
                cc[i]++;
                valL /= i;
                maxval = max (maxval, i);
            }
        }
    }
    if (valL > 1)
    {
        cc[valL]++;
        maxval = max (maxval, valL);
    }
}

inline LL power (LL a, LL num)
{
    LL res = 1;
    for (LL i = 1; i <= num; i++)
        res *= a;

    return res;
}

int main()
{
//    CPPFF;
    LL t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";
        LL A, B, L;
        cin >> A >> B >> L;
        PP(A, B, L);

        LL ttmax, res = 1;
        bool is_valid = true;
        for (LL i = 2; i <= maxval; i++)
        {
            ttmax = max (aa[i], bb[i]);
            if (ttmax > cc[i])
            {
                is_valid = false;
                break;
            }

            else if (ttmax < cc[i])
            {
                res *= power (i, cc[i]);
            }

            if (aa[i] > 0)
                cnta--;

            if (bb[i] > 0)
                cntb--;
        }

        if (!is_valid)
            cout << "impossible" << endl;

        else
        {
            if (cnta == 0 && cntb == 0)
                cout << res << endl;

            else
                cout << "impossible" << endl;
        }
    }
    return 0;
}

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

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

LL aa[maxn], bb[maxn], cc[maxn], lena, lenb, lenc;

LL maxval, cnta, cntb;

LL PP (LL vala, LL valb, LL valL)

{

lena = lenb = lenc = 0;

memset (aa, 0, sizeof (aa));

memset (bb, 0, sizeof (bb));

memset (cc, 0, sizeof (cc));

cnta = cntb = 0;

for (LL i = 2; i * i <= vala; i++)

{

if (vala % i == 0)

{

cnta++;

while (vala % i == 0)

{

aa[i]++;

vala /= i;

}

if (vala > 1)

{

aa[vala]++;

cnta++;

}

for (LL i = 2; i * i <= valb; i++)

{

if (valb % i == 0)

{

cntb++;

while (valb % i == 0)

{

bb[i]++;

valb /= i;

}

if (valb > 1)

{

bb[valb]++;

cntb++;

}

maxval = -INF;

for (LL i = 2; i * i <= valL; i++)

{

if (valL % i == 0)

{

while(valL % i == 0)

{

cc[i]++;

valL /= i;

maxval = max (maxval, i);

}

if (valL > 1)

{

cc[valL]++;

maxval = max (maxval, valL);

}

inline LL power (LL a, LL num)

{

LL res = 1;

for (LL i = 1; i <= num; i++)

res *= a;

return res;

}

int main()

{

// CPPFF;

LL t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

LL A, B, L;

cin >> A >> B >> L;

PP(A, B, L);

LL ttmax, res = 1;

bool is_valid = true;

for (LL i = 2; i <= maxval; i++)

{

ttmax = max (aa[i], bb[i]);

if (ttmax > cc[i])

{

is_valid = false;

break;

}

else if (ttmax < cc[i])

{

res *= power (i, cc[i]);

}

if (aa[i] > 0)

cnta--;

if (bb[i] > 0)

cntb--;

}

if (!is_valid)

cout << "impossible" << endl;

else

{

if (cnta == 0 && cntb == 0)

cout << res << endl;

else

cout << "impossible" << endl;

}

return 0;

}

lightoj1213

lightoj1255

超客的水墨烟雨

lightoj1215

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论

2024年10月
一	二	三	四	五	六	日
« 6月
	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