Задачи за тренинг (2011/2012)

Задача 1а. Да се напише програма за превръщане на естествено число от двоичен запис (в двоична бройна система) в десетичен (в десетична бройна система) и обратно.

Вход:
На стандартния вход се задава редица от двойки числа (примери), като всяка двойка е на отделен ред. Първото число от двойката е 2 или 10, и показва каква е основата на бройната система, в която е записано второто число, което е по-малко от 106.

Изход:

За всеки пример (двойка числа) от входа се извежда едно число на отделен ред - записа на второто число в другата бройна система.

Пример:
10 8
2 1

Решение на примера:
1000
1

Задача 1b. От основната теорема на аритметиката следва, че всяко естествено число n > 1 може да се представи единствен начин във вида n = pkm, където p е просто число,  k и m са естествени числа и m не се дели на p. Да се напише програма, която намира k при зададени n и p.

Вход:
Първото число от входа е броят на примерите на входа. Следващите двойки числа са n и p. Всички числа са по-малки от 106.

Изход:
За всеки пример от входа се извежда на отделен ред намереното число k.

Пример:
3
12 2
100 7
29 29


Решение на примера:
2
0
1

Бележка: 12 = 22x3, 100 = 70x100, 29 = 291x1 (тук x означава умножение).