JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Algorithm Matches SRM 534 Re: Editorial Revision History (3 edits)
Re: Editorial (response to post by espr1t)
Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):

In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.

At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.

my code:
HASH <long long, long long> hash;
for_each x in special number
    if n mod x == 0 and gcd(x, n / x) == 1
    {
        for_each element i in hash
        {
             if (n mod (i->first * x) == 0) {
                  hash[i->first * x] += i->second;
             }
        }
        hash[x] ++;
    }
return hash[n];


It is not difficult to proof that at every moment the size of hash will always not larger than 2^K.

for example, let's assume N = 2^1 * 3^3 * 5^2 * 7^4
and your bit status may be: 0 1 1 0
but I directly use their product: 3^3 * 5^2 as an status in my hashmap.
Re: Editorial (response to post by espr1t)
Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):

In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.

At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.

my code:
--------------------------------------------
HASH <long long, long long> hash;
for_each x in special number
    if n mod x == 0 and gcd(x, n / x) == 1
    {
        for_each element i in hash
        {
             if (n mod (i->first * x) == 0) {
                  hash[i->first * x] += i->second;
             }
        }
        hash[x] ++;
    }
return hash[n];
Re: Editorial (response to post by espr1t)
Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):

In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.

At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.

my code:
--------------------------------------------
HASH <long long, long long> hash;
for_each x in special number
if n mod x == 0 and gcd(x, n / x) == 1
{
for_each element i in hash
{
if (n mod (i->first * x) == 0) {
hash[i->first * x] += i->second;
}
}
hash[x] ++;
}
return hash[n];
Re: Editorial (response to post by espr1t)
Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):

In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.

At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.