# PBinfo #3216 – descdiv – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Dat n, un număr natural nenul, să se determine numărul de posibilități de a-l scrie pe n ca sumă de divizori ai săi. Pentru că acest număr poate fi foarte mare, se va determina modulo 123457.

Date de intrare
Programul citește de la tastatură numărul n.

Date de ieșire
Programul va afișa pe ecran numărul de descompuneri, modulo 123457.

Restricții și precizări

1 ≤ n ≤ 10.000

Exemplu:
Intrare

6
Ieșire

8
Explicație
Cele 8 modalități sunt: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3, 1+1+2+2, 2+2+2, 1+2+3, 3+3, 6.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define MOD 123457
using namespace std;
int dp[10005], n;
int d[2000], k;
/// dp[i]=numarul de posibilitati de a-l scrie pe i ca suma de divizori ai lui n
void Divizori(int n)
{
    int i;
    for (i = 1; i * i < n; i++)
        if (n % i == 0)
        {
            d[++k] = i;
            d[++k] = n / i;
        }
    if (i * i == n) d[++k] = i;
    sort(d + 1, d + k + 1);
}
int main()
{
    int i, j, x;
    cin >> n;
    Divizori(n);
    /// dinamica
    for (i = 1; i <= k; i++)
    {
        x = d[i];
        dp[x]++;
        if (dp[x] == MOD) dp[x] = 0;
        for (j = 1; j <= n - x; j++)
            dp[j + x] = (dp[j + x] + dp[j]) % MOD;
    }
    cout << dp[n] << "\n";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3216)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3216/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3216/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)