Invers modular X42716


Statement
 

pdf   zip

html

L’invers modular d’un enter a mòdul m és un enter x tal que:

ax  ≡ 1   mod  m

Donats a i m troba x, l’invers modular d’a mòdul m amb 1 ≤ x ≤ m. En cas que no existeixi un invers modular indica-ho.

Entrada

L’entrada consisteix en diversos casos, cada cas consta d’una línia, hi ha com a molt 105 línies. Cada línia conté dos enters a i m amb 1 ≤ a < m ≤ 108.

Sortida

Escriviu un enter per línia: x, l’invers modular d’a mòdul m amb 1 ≤ x ≤ m. En cas que no existeixi un invers modular escriviu "Sense solucio".

Pista

Planteja el problema en termes d’equacions diofàntiques

Public test cases

  • Input

    1 3
3 5
1 15
2 16
3 12
66958119 93770126
74634 491265

    Output

    1
2
1
Sense solucio
Sense solucio
52155667
Sense solucio
    • Information
    Author
    Max Balsells
    Language
    Catalan
    Official solutions
    C++
    User solutions