drifter_kabir's blog

Need Help...
By drifter_kabir, history, 4 years ago, In English

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.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Your rating graph is the definition of persistence.

→ Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

There is an infinite number of integers whose digit sum is exactly $$$a^b$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry I missed one thing. The sum of all numbers whose each digit is non-zero.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is there a modulo?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, 1e9+7

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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

          $$$A \begin{pmatrix} s_{i1} \\ \vdots \\ s_{i9} \\ c_{i1} \\ \vdots \\ c_{i9} \\ 1 \end{pmatrix} = \begin{pmatrix} s_{i+1,1} \\ \vdots \\ s_{i+1,9} \\ c_{i+1,1} \\ \vdots \\ c_{i+1,9} \\ 1 \end{pmatrix} \qquad \text{ for all } i.$$$

          Find this matrix and then calculate $A^{a^b}$ (Fermat's little theorem will help you exponentiate).

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 4   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              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.

              → Reply