Cod sursa(job #2253161)

Utilizator BeginngerThe Mighty Ginger Beginnger Data 3 octombrie 2018 18:36:38
Problema Descompuneri Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("desc.in");
ofstream g("desc.out");
long long n, k;
int dp[2001][2001];
long long divi[7500], nr;
map<long long, int>d;
int main()
{
    f >> n >> k;
    for(long long i = 1; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            if(i != 1)
                divi[++nr] = i;
            if(i != n / i)
                divi[++nr] = n/i;
        }
    }
    sort(divi + 1, divi + nr + 1);
    divi[0] = 1;
    for(int i = 1; i <= nr; ++i)
        d[divi[i]] = i;
    dp[0][nr] = 1;
    for(int i = 0; i <= nr; ++i)
        for(int j = i+1; j <= nr; ++j)
        {
            if(divi[j] % divi[i] != 0)
                continue;
            int rap = divi[j]/divi[i];
            if(d.find(rap) == d.end())
                continue;
            int x = d[rap];
            for(int e = nr; e >= x; --e)
                dp[j][x] += dp[i][e];
        }
    long long sol = 0;
    for(int i = 1; i <= nr; ++i)
        sol += dp[nr][i];
    g << sol << '\n';
    return 0;
}