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.
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
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.
Name |
---|
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.