
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. 