3676 - ABK1K2

Cerința

Se dau patru numere naturale a, b, k1, k2. Determinați numărul de submulțimi formate din două elemente numere naturale x și y, cu x și y cuprinse între a și b, astfel încât cel mai mare divizor comun al lui x și y să fie multiplu de k1 sau multiplu de k2.

Date de intrare

Fișierul de intrare conține patru numere, câte unul pe rând, în ordine: a, b, k1, k2 cu semnificația de mai sus.

Date de ieșire

În fișierul de ieșire se va scrie pe prima linie valoarea cerută.

Restricții și precizări

• a și b sunt cuprinse între 1 și inclusiv 109, a ≤ b.
• k1 și k2 sunt cuprinse între 2 și 109 inclusiv.
• perechile pentru care avem x = y nu se numără.

Exemplul 1

abk1k2.in

4

10

2

4

abk1k2.out

6

Explicație

Submulțimile care se numără sunt: 4, 6 4, 8 4, 10 6, 8 6, 10 8, 10.

Exemplul 2

abk1k2.in

10

20

3

abk1k2.out

Date invalide: Nu sunt suficiente date in fisierul de intrare

Rezolvare

<syntaxhighlight lang="python" line>

1. 3676 abk1k2

from math import gcd

def verificare_date_intrare(a, b, k1, k2):

 # Verificăm dacă a și b sunt în intervalul specificat
 if not (1 <= a <= b <= 10**9):
   return False
 
 # Verificăm dacă k1 și k2 sunt în intervalul specificat
 if not (2 <= k1 <= 10**9 and 2 <= k2 <= 10**9):
   return False
 
 return True

def numar_submultimi(a, b, k1, k2):

 if not verificare_date_intrare(a, b, k1, k2):
   return "Date invalide: Parametrii introdusi sunt incorecti."
 
 count = 0
 for x in range(a, b + 1):
   for y in range(x + 1, b + 1):
     if gcd(x, y) % k1 == 0 or gcd(x, y) % k2 == 0:
       count += 1
 return count

def main():

 # Citim datele de intrare
 with open("abk1k2.in", "r") as f:
   linii = f.readlines()
 
 # Eliminăm liniile goale și spațiile suplimentare
 linii = [linie.strip() for linie in linii if linie.strip()]
 
 # Verificăm dacă avem suficiente linii pentru a extrage datele
 if len(linii) != 4:
   # Scriem mesaj de date invalide în fișierul de ieșire
   with open("abk1k2.out", "w") as f:
     f.write("Date invalide: Nu sunt suficiente date in fisierul de intrare")
   return
 
 # Extragem datele de intrare
 a = int(linii[0])
 b = int(linii[1])
 k1 = int(linii[2])
 k2 = int(linii[3])
 
 # Calculăm numărul de submulțimi dorit
 rezultat = numar_submultimi(a, b, k1, k2)
 
 # Scriem rezultatul în fișierul de ieșire
 with open("abk1k2.out", "w") as f:
   f.write(str(rezultat))

if __name__ == "__main__":

 main()

</syntaxhighlight>