Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### sahal's blog

By sahal, history, 5 months ago, ,

can anyone help me? How to solve this problem in Extended Euclid algorithm??? https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1574

• 0

 » 5 months ago, # |   0 Why Extended Euclid algorithm? We can apply simple logic. Let's represent the number $N$ as $10*a+b$ where $b \lt 10$ and $M = a$. So we are given the number $X=N-M=10*a+b-a = 9*a+b$. We can easily see that if $b \neq 0$ and $b \neq 9$ (i.e. $X$ % $9 \neq 0$) then $a = X / 9$, $b = X$ % $9$ and $N$ can be unique restored. If $b$ is $0$ or $9$ (i.e. $X \% 9 = 0$) then for $N$ we have two possibilities: $10*(X/9)-1$ and $10*(X/9)$.
•  » » 5 months ago, # ^ |   0 Thank you , I know this but the problem was given in Extended Euclid Volume. That's why i wanted to know that approach.