Pre-requisites : prime factorisation, pollard-rho heuristics
Solution :
The problem requires nothing more than but factorizing the integer number, as it is stated in the statement.
The basic approach is the following:
First, we determine, whether the given integer is smaller than 1018;
If it’s so, we can use long long data type, that is faster and simpler to use. We can brute-force all the primes not greater than 106 and check whether they divide the given integer or not. After we divide the given number by all its’ divisors not greater than 106, it will be either 1, either a prime, either a product of two large primes.
If the number is actually greater than 1018, we should use bignums arithmetic. That means that all the operations become slower than in the long long case, so we can brute force all the prime divisors smaller than some constant that can be figured out by experiments, depending of the speed of the solution.
This solution is easy to code, but it also has some obvious disadvantages. Moreover, at the cases if the second type this approach won’t work at all, because the test cases of the second type are basically a product of two big primes.
In order to make this solution better, there are two ways. At first, you should speed the bignum arithmetic up as much as possible. At second, you can consider using some better methods. For example, Pollard-Rho. A lot of the information on non-trivial factorization algorithms can be actually found on the internet.
At the end, I’d like to note that it seems best to solve the 4-th group, rather than other ones. Even the brute-force solution is capable of finding a hundred divisors for the test of the fourth group.
Since just calculating as fast as possible seemed a bit naive, I came up with next heuristic.
Note how the testcases are generated.
2 ≤ N ≤ 10^1000, all the prime divisors of N don’t exceed 10^18
2 ≤ N ≤ 10^1000, the length of N is chosen randomly. All the digits are generated randomly
…
Note how score is calculated:
the sum of M² over all the test cases in this file
This means that finding one extra prime factor for a number scores better if you do it for a number where there are already many factors found. According to the test case generation the chances of having a lot of factors will certainly differ. Also, you could lose a lot of useless computations to a very big prime. And for random numbers this chance is realistic to occur.
Combining this knowledge leads to following strategy:
for each number in the test file, check the first X primes and count the number of total divisors.
sort by most found primes, since they have a higher chance of having more primes to follow / leading to a higher score.
calculate as long time permits the Y first prime factors for the Z first numbers with the biggest number of factors so far
each time all first Y factors of one of the Z first numbers are done for a number (or the rest of the number becomes 1), we take the next in line, with highest chance of giving us a better score. And just go on with the iterations. (as long time permits)
This strategy improved a lot for me. Configuring X, Y and Z of course is key for a good score.
I experimented for example with (X=100, Y=200000, Z=10)
Simple optimization techniques:
When you read a big number that ends with a zero, you can cut trailing zero’s and just each time add 2 factors (2 and 5) to the result of that number. This at least decreases the parsing and calculation a bit.
As the editorial states you can use a variant for long and one for big numbers, for speed of calculations. I also switched to the long calculations from the moment my value was in the long_range.
Get a fast prime generation algorithm, I fine tuned it a lot during the contest. A lot of reading to be found about it on the interwebs.
Stop useless calculations when you know you’re having a prime left. (e.g. lastUsedPrime² > numberAfterPreviousCalculation)
my question is for the setter
why haven’t u generated primes , and u have checked for each factor from 1 to 1000 just once ,how will it calculate for a factor like 2*2 (let s take the number to be 4) since it will go to 2 just once.
@kishlay_raj for 4 when d=2 the while(ok) loop runs 2 times each time dividing the content of the array and leaving the quotient and now when d=3 array content is just 1 and due to which x is always non-zero and always while(ok) terminates after the first loop inside of it…
