28ος ΠΔΠ Καμπ (juniors)
Άθροισμα Κύβων (sumofcubes)
Κάποιοι φυσικοί αριθμοί, όπως ο \(17\), μπορούν να γραφούν ως άθροισμα τριών κύβων φυσικών αριθμών: \(17 = 1^3 + 2^3 + 2^3\). Άλλοι, όπως ο \(42\), δεν μπορούν να γραφούν σε αυτή τη μορφή. Κάποιοι φυσικοί αριθμοί, όπως ο \(251\), μπορούν να γραφούν σε αυτή τη μορφή με περισσότερους του ενός τρόπους: \(251 = 1^3 + 5^3 + 5^3 = 2^3 + 3^3 + 6^3\).
Γράψτε ένα πρόγραμμα που να διαβάζει κάποιους φυσικούς αριθμούς και να βρίσκει με πόσους διαφορετικούς τρόπους καθένας από αυτούς μπορεί να γραφεί ως άθροισμα τριών κύβων φυσικών αριθμών.
Αρχεία Εισόδου (sumofcubes.in):
Η πρώτη γραμμή της εισόδου θα περιέχει το πλήθος \(T\) των αριθμών που θα δοθούν στη συνέχεια. Οι επόμενες \(T\) γραμμές θα περιέχουν κάθε μία ακριβώς έναν φυσικό αριθμό \(N_i\).
Αρχεία Εξόδου (sumofcubes.out):
Η έξοδος πρέπει να αποτελείται από \(T\) γραμμές, κάθε μία από τις οποίες πρέπει να περιέχει ακριβώς έναν ακέραιο αριθμό, το πλήθος των τρόπων με τους οποίους ο αντίστοιχος αριθμός \(N_i\) της εισόδου μπορεί να γραφεί ως άθροισμα τριών κύβων φυσικών αριθμών.
Παράδειγμα Αρχείου Εισόδου - Εξόδου:
| sumofcubes.in | sumofcubes.out |
|---|---|
| 6 17 42 251 0 5104 1003 |
1 0 2 1 3 0 |
Εξήγηση παραδείγματος: Το \(17 = 1^3 + 2^3 + 2^3\) γράφεται με έναν τρόπο ως άθροισμα τριών κύβων. Το \(251 = 1^3 + 5^3 + 5^3 = 2^3 + 3^3 + 6^3\) γράφεται με δύο τρόπους ως άθροισμα τριών κύβων. Το \(0 = 0^3 + 0^3 + 0^3\) γράφεται με έναν τρόπο ως άθροισμα τριών κύβων. Το \(5104 = 1^3 + 12^3 + 15^3 = 2^3 + 10^3 + 16^3 = 9^3 + 10^3 + 15^3\) γράφεται με τρεις τρόπους ως άθροισμα τριών κύβων. Τέλος, οι αριθμοί \(42\) και \(1003\) δεν μπορούν να εκφραστούν ως άθροισμα τριών κύβων.
Περιορισμοί
- \(1 \leq T \leq 10.000\).
- \(0 \leq N_i \leq 1.000.000.000\).
- Όριο χρόνου εκτέλεσης: \(1\) sec.
- Όριο μνήμης: \(16\) MB.