Div 1 250: FoxAndGCDLCM
You get two numbers: L and G, both between 1 and 10^12, inclusive. Find two numbers A and B such that gcd(A,B) = G, lcm(A,B) = L and (A+B) is as small as possible.
This is the approach I took during the match: The number of distinct prime factors for a number less than 10^12 is very low (Remembering last match, this number is definitely less than 15). We can extract prime factors of a number N in O(sqrt(N)) time. So, imagine we extracted the distinct prime factors of G and L, since by definition L is a multiple of G, then G will never have a prime factor that is not a prime factor of L. (If L is not a multiple of G, return -1 instantly). In fact, since we are talking about distinct prime factors, you also need, for each distinct factor, the number of times it appears as a factor of G and L. (For example, for G=40, the factorization is 2*2*2*5, 2 appears three times and 5 one time). Note that A and B both have to be multiples of G. This means that they both have to be multiples of each of the prime factors of G raised to the number of times the factor appears in G. The number of times a factor appears in L will be greater than or equal to the number of times it appears in G. This means that the minimum number of times a factor appears in A or B is equal to the number of times it appears in G. Similarly, the maximum number of times the factor appears in A or B is equal to the number of times it appears in L. Note that a factor cannot appear a number of times different to the minimum or the maximum (else the lcm rule wouldn't work). More so, if a factor appears the minimum number of times in A, it must appear the maximum number of times in B and viceversa.
So we have less than 15 prime factors and a decision, for each of them to place in A or B. You can just try all different 215 ways to make these decisions. For each of them, calculate A and B, then pick the minimum A+B possible.
//Death to long!
typedef long long int64;
#define long int64
#define var(q,s) typeof(s) q = s
#define for_each(q, s) for( var(q,s.begin()); q!=s.end(); q++)
struct FoxAndGCDLCM
{
//Extract each prime factor,
// and the number of times it appears in x:
map<long, int> factorize(long x)
{
var(p, 2ll);
map<long, int> res;
//no need to check for a factor larger than sqrt(p)
while (p <= x / p) {
while (x % p == 0) {
res[p]++;
x /= p;
}
p ++;
}
if (x != 1) {
res[x]++;
}
return res;
}
long get(long G, long L)
{
if (L % G != 0) {
return -1;
}
var( gfactors, factorize(G));
var( lfactors, factorize(L));
pair<int, long> res = make_pair(1, -1ll);
//t different prime factors.
int t = lfactors.size();
// try each possible combination of decisions.
// 2^t in total (same as saying 1<<t).
for (int mask=0; mask<(1<<t); mask++) {
long A = G, B = G;
int i = 0; //so we know the index of the prime factor.
for_each(q, lfactors) {
long p = 1;
for (int j=gfactors[q->first]; j < q->second; j++) {
p *= q->first;
}
//decide...
if (mask & (1<<i)) {
A *= p;
} else {
B *= p;
}
i++;
}
res =std::min(res, make_pair(0, A+B) );
}
return res.second;
}
};
#undef long
That's the code I wish I coded, compare it with this monstrousity if you wish...
Now, that solution is still quite lame. Compare it with this one: L must be a multiple of G. Ok, now consider that A and B must be multiples of G. But what if we set a = A / G and b = B / G. Then a*b would hold all the factors that are not common to A nor B. a*b is also equal to L/G (try L = A*B / G as a base). Also notice that A+B = a*G + b*G = G * (a+b) and thus minimizing a*b yields the answer. Then since a*b are factors of L/G, you can just try all pairs (a,b) of numbers such that a*b = L/G (ie: extract the divisors of L/G in O(sqrt(L/G)). However, make sure the pairs (a,b) are coprime (again, else the lcm rule wouldn't hold). Notice that these two solutions do exactly the same thing... But the new solution looks like this:
//Death to long!
typedef long long int64;
#define long int64
//Euclid's GCD
template<class T> T gcd(T a, T b)
{
while (b != 0) {
T c = b;
b = a % b;
a = c;
}
return a;
}
struct FoxAndGCDLCM
{
long get(long G, long L)
{
if (L % G != 0) {
return -1;
}
pair<int, long> res = make_pair(1, -1);
long ab = L/G;
// divisors of ab
for(long a=2; a <= ab/a; a++) {
if (ab % a == 0) {
//try all pairs (a,b)
long b = ab / a;
if (gcd(a,b) == 1) { //pair-wise coprime?
res = std::min(res, make_pair(0, (a + b)*G ) );
}
}
}
return res.second;
}
};
#undef long
Challenge phase et all
I had some ideas for div1 500, nothing concrete I think I will post something later. I avoid any challenge during the challenge phase.
Opinions?
The problems I opened seemed good. Div1 250 was fun. I was just too slow.
0 comments:
Post a Comment