Popcounts
Турнир за Купата на Декана, 2011
Time Limit: 0.8s, Memory Limit: 64MiB
"Двоично Тегло" на едно число е броят единици, които то има в двоичния си запис. Например теглото на числото 42 е три, тъй като двоичното му представяне е 101010. 1337 от друга страна има тегло шест (двоичното му представяне е 10100111001).
Ели генерира случайни числа и смята сумата на техните двоични тегла. Защо тя прави това не е ясно, но все пак вие решавате да я впечатлите, като напишете програма, която бързо смята тази сума.
Ели генерира числата по следния начин: в началото тя определя пет цели числа N, F, A, B, и M. Редицата има N члена, първият от които е F. Всеки следващ се образува, като предходният се умножи по A, после се прибави B и се вземе остатъка на резултата при деление на M. Тоест:
Ели генерира случайни числа и смята сумата на техните двоични тегла. Защо тя прави това не е ясно, но все пак вие решавате да я впечатлите, като напишете програма, която бързо смята тази сума.
Ели генерира числата по следния начин: в началото тя определя пет цели числа N, F, A, B, и M. Редицата има N члена, първият от които е F. Всеки следващ се образува, като предходният се умножи по A, после се прибави B и се вземе остатъка на резултата при деление на M. Тоест:
- S1 = F
- Si = (Si-1 * A + B) % M, за i = 2, 3, ..., N.
Вход
На единствен ред на стандартния вход ще бъдат зададени петте цели числа N, F, A, B, и M.
Изход
На стандартния изход изведете едно единствено цяло число – сумата на двоичните тегла на генерираните числа.
Ограничения
- 1 ≤ N ≤ 20,000,000
- 0 ≤ F, A, B < M ≤ 1,000,000,007
Примерен Вход | Примерен Изход |
---|---|
5 42 3 5 113 | 17 |
1337 7 17 9 12345 | 8837 |
12345678 123 41 2 1000000000 | 189462355 |
В първия пример генерираните числа са 42, 18, 59, 69, и 99. Техните двоични тегла са съответно 3, 2, 5, 3, и 4, които дават сума 17.