Λίγη Θεωρία Αριθμών

[nik324]

Έστω ότι έχουμε μια ακολουθία από n μη ταξινομημένους αριθμούς...Και ένα τυχαίο αριθμό x...Αυτό που θέλω να κάνω είναι να δω αν υπάρχουν δυο αριθμοί από την ακολουθία που το πηλίκο τους να ισούτε με x...

O πιο απλός τρόπος είναι να τσεκάρω τους συνδιασμούς όλων τον αριθμών και να βρίσκω αν καποιος ισούτε με x...

Aν όμως η ακολουθία των αριθμών ήταν ταξινομημένη μήπως θα αποκτούσαν οι αριθμοί κάποια ιδιότητα και δεν θα έπρεπε να τσεκάρω όλους τους δυνατούς συνδιασμούς??

[mphxths]

Δ/δ = π + υ (στην περιπτωση μας θεωρω οτι εννοεις υ=0 , δηλαδη τελεια διαιρεση)

 

και το π ειναι το χ που αναφερεις.

 

θα μπορουσες να τους ταξινομησεις τους αριθμους και να αρχιζεις να πολλαπλασιαζεις το χ με ολους τους αριθμους που ειναι μικροτεροι ή ισοι του και να βλεπεις αν το γινομενο υπαρχει μεσα στην ακολουθια που εχεις.

Αν υπαρχει τοτε το γινομενο ειναι το Δ και ο αριθμος που πολλαπλασιασες τον χ το δ ...και αρα εχεις τους αριθμους σου...

 

και παλι οι ελεγχοι θαναι καμποσοι...αναλογως βεβαια και το μεγεθος της ακολουθιας...

 

Αυτη η ιδεα μου ρθε τετοια ωρα

 

ΕΔΙΤ: τωρα που το σκεφτομαι θα πρεπει να πολλαπλασιασεις τον χ με οοολους τους αριθμους...αρα ακυρο δεν μας κανει.

[nik324]

Nαι δεν μου κάνει...Αυτό που προσπαθώ να καταφέρω είναι να κάνω λιγότερες συγκρίζεις απο το να συγκρλινω όλους τους αριθμούς ανά δύο....

[Bspus]

Μπορεις να αποφυγεις καποιες συγκρισεις.

Υποθετω οτι:

μιλαμε για θετικους ακεραιους εκτος του 0.

Δεν συμπεριλαμβανεται και το x και το 1 στο ιδιο συνολο. Αν συμπεριλαμβανονται, εχεις αυτοματα λυση

 

 

A1, A2, A3, ... Az-1, Az, X B1, B2, B3, B4, B5...

 

Μπορεις να αποφυγεις ολες τις διαιρεσεις μεταξυ των A, Η μεγαλυτερη τιμη που μπορει να πιασει η διαιρεση ειναι Αz/A1 που στην περιπτωση που το Α1=1 παλι ειναι μικροτερο του Χ

 

Δεν μπορω να σκεφτω κατι αλλο αυτη τη στιγμη

 

edit

Διαιρεις ολα τα Β με το Χ και οποιο ειναι τελεια διαιρεση ψαχνεις να βρεις αν υπαρχει ως στειχειο του συνολου