nicuvlad76

Untitled

Dec 11th, 2020
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MOD 123457
  3. using namespace std;
  4.  
  5. int dp[10005], n;
  6. int d[2000], k;
  7. /// dp[i]=numarul de posibilitati de a-l scrie pe i ca suma de divizori ai lui n
  8.  
  9. void Divizori(int n)
  10. {
  11. int i;
  12. for (i = 1; i * i < n; i++)
  13. if (n % i == 0)
  14. {
  15. d[++k] = i;
  16. d[++k] = n / i;
  17. }
  18. if (i * i == n) d[++k] = i;
  19. sort(d + 1, d + k + 1);
  20. }
  21.  
  22. int main()
  23. {
  24. int i, j, x;
  25. cin >> n;
  26. Divizori(n);
  27. /// dinamica
  28. for (i = 1; i <= k; i++)
  29. {
  30. x = d[i];
  31. dp[x]++;
  32. if (dp[x] == MOD) dp[x] = 0;
  33. for (j = 1; j <= n - x; j++)
  34. dp[j + x] = (dp[j + x] + dp[j]) % MOD;
  35. }
  36. cout << dp[n] << "\n";
  37. return 0;
  38. }
Add Comment
Please, Sign In to add comment