Submission #24494

---

Source Code Expand

module main;

import std.stdio;
import std.array;
import std.string;
import std.conv;
//import std.math;
import std.algorithm;
import std.range;
import std.typetuple;
import std.functional;
const mod = 10_0000_0007;


void main()
{
    solve_D();
}

void solve_D()
{
    auto buf = readln().strip().split();
    int n = buf[0].to!int();
    int m = buf[1].to!int();
    if (n < 0)
    {
        n = -n;
    }
    int[int] power;
    foreach (prime; known_primes())
    {
        if (n % prime == 0)
        {
            power[prime] = 0;
            while (n % prime == 0)
            {
                power[prime] += 1;
                n /= prime;
            }
        }
    }
    // (いま) n = 1 なら (もとの) n の素因数は小さいものばかり。
    // そうでない場合は大きい素因数だけの積になっているが、それは単一の素数にほかならない。
    if (1 < n)
    {
        power[n] += 1;
    }
    assert(n); // check
    // 符号の処理: 最後以外は自由に選べる。
    ulong ret = 1;
    foreach (i; 1..m)
    {
        ret *= 2;
        ret %= mod;
    }
    // ここがメイン。
    foreach (p, e; power)
    {
        ret *= partition(e, m);
        ret %= mod;
    }
    writefln("%d", ret);
}

int[] known_primes()
{
    const M = 32768;
    bool[M] not_prime;
    not_prime[0] = true;
    not_prime[1] = true;
    foreach (i; 2..200)
    {
        if (not_prime[i])
        {
            continue;
        }
        foreach (j; iota(i+i, M, i))
        {
            not_prime[j] = true;
        }
    }
    int[] ret;
    foreach (i; 2..M)
    {
        if (!not_prime[i])
        {
            ret ~= i;
            //            debug { writef("%d, ", i);}
        }
    }
    return ret;
}

int partition(int e, int n)
out (result)
{
    assert(0 <= result && result < mod);
}
body
{
    ulong[][] dp;//[n+1][e+1] dp;
    dp.length = n+1;
    foreach (i; 0..(n+1))
    {
        dp[i].length = e+1;
    }
    dp[0][0] = 1;
    foreach(i; 0..n)
    {
        foreach (j; 0..(e+1))
        {
            foreach (jj; 0..(j+1))
            {
                dp[i+1][j] += dp[i][jj];
                if (mod <= dp[i+1][j])
                {
                    dp[i+1][j] -= mod;
                }
            }
        }
    }
    return cast(int)(dp[n][e]);
}

Submission Info

Judge Result