Given a & b(where(1<=a,b<=20), find sum of all integers whose digit sum is exactly $$$a^{b}$$$.
Return sum%10^9+7
Update: Sorry I missed one thing. The sum of all numbers whose each digit is non-zero.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.05.2024 15:06:33 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Your rating graph is the definition of persistence.
There is an infinite number of integers whose digit sum is exactly $$$a^b$$$.
Sorry I missed one thing. The sum of all numbers whose each digit is non-zero.
Is there a modulo?
Yes, 1e9+7
I believe the following should work. Denote by $$$s_{ij}$$$ the sum of all zero-free numbers with digit sum $$$i$$$ and last digit $$$j$$$ and $$$c_{ij}$$$ be the number of all such numbers. There exists a matrix $$$A$$$ such that
Find this matrix and then calculate $A^{a^b}$ (Fermat's little theorem will help you exponentiate).
Wait, we don't know if Fermat's theorem or Euler's theorem applies for matrices right? Isn't it more about Binary Exponentiation? What is the modulo of a matrix?
Adding more: I think you can't say that $$$ A^{a^{b}} \mod p $$$ gives same answer as $$$A^{ ( a^b \mod {p-1} ) } \mod p $$$, where $$$ A \mod p $$$ is taking element wise modulo of all entries in $$$A$$$.
Since multiplying matrices only has multiplication and addition operations, we can definitely agree that $$$ (A*B) \mod p $$$ is same as $$$ ( A \mod p ) * ( B \mod p ) \mod p $$$. But exponentiation is different, to take modulo of the exponent by $$$phi(p)$$$, you need to show that $$$ A^{phi(p)} $$$ will be identity matrix.
Whoops, yeah you're right. If A turns out to be diagonalizable then it should still work (and we can try to make it work in some other cases probably too), but in this case it's probably better to just calculate $$$a^b$$$ in 128-bit integers or something.