numere
Цифърко е
голям фен на
числата. Днес
той играе с
числа, които
имат N цифри
и които са
записани в
бройна
система с
основа B. Нека
NR=x0x1...xN-1 е
такова число,
записано в
бройна
система с основа
B (x0,x1 и т.н. представят
цифрите на
числото NR, записани
отляво-надясно).
Ние
дефинираме
образ на това
число като друго
число I(NR)=i0i1…iN-2 за което
е изпълнено,
че ip=min(xp,xp+1). Имайки
много време, Цифърко
е започнал
да мисли как
да пресмята
за всяко възможно
число от N цифри
при основа B произведенията
на цифрите на
образа му и да
получава
сумата на
тези произведения.
Задача
Напишете
програма,
която да
помага на Цифърко да
прави такива
пресмятания и
да намира
търсената
сума за
приемливо време.
Вход
Единственият
ред на
входния файл numere.in съдържа
две
положителни
цели числа N и B, отделени
с един
интервал.
Изход
Единственият
ред на
изходния
файл numere.out трябва
да съдържа
сумата, която
Цифърко търси. Понеже
резултатът
може да е
много голям,
достатъчно е
да се изведе
само
остатъкът от
делението на
резултата с
числото 666013.
Ограничения
2 <= N <= 20000
2 <= B <= 1000
Числата
може да
започват с 0.
Примери
numere.in |
numere.out |
Обяснение |
2 4
|
14 |
NR=00, I(NR)=0, прибавяме 0 NR=01, I(NR)=0, прибавяме 0 NR=02, I(NR)=0, прибавяме 0 NR=03, I(NR)=0, прибавяме 0 NR=10, I(NR)=0, прибавяме 0 NR=11, I(NR)=1, прибавяме 1 NR=12, I(NR)=1, прибавяме 1 NR=13, I(NR)=1, прибавяме 1 NR=20, I(NR)=0, прибавяме 0 NR=21, I(NR)=1, прибавяме 1 NR=22, I(NR)=2, прибавяме 2 NR=23, I(NR)=2, прибавяме 2 NR=30, I(NR)=0, прибавяме 0 NR=31, I(NR)=1, прибавяме 1 NR=32, I(NR)=2, прибавяме 2 NR=33, I(NR)=3, прибавяме 3 |
Time limit: 1.8 seconds/test
Mircea Paşoi
University of Bucharest,
Mathematics & IT Department
bogdanpasoi@yahoo.com
(превод
на български:
Емил
Келеведжиев)