simplecomplex's blog

Repeated Digit Sum of A^B
By simplecomplex, history, 6 years ago, In English

Here's the problem from last year's ACM ICPC Dhaka Regional Preliminary Round.

It says to calculate sod(n) [sum of digits of n] while n >= 10. Here n = a^b, (0<= a,b <= 10^50,000 and a+b>0 ) Any thoughts on how to solve this?

  • Vote: I like it
  • +6
  • Vote: I do not like it

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

hint: divisibility rule by 9

At least if I correctly understood problem (I don't have access to your link)

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

It can be proven that the repeated digit sum of N is 1 + (N - 1) mod 9, so what you basically need to calculate ab mod 9.

It is well known that ab ≡ ab mod φ(M) (mod M) for (a, M) = 1.
A less known fact is ab ≡ aφ(M) + b mod φ(M) (mod M), for any a, M and b ≥ log(M). Using this and some case walk you can solve the problem.

However, there is another easy solution. That is, write b = b0 + b1·10 + b2·102 + ... + bn·10n. Now —

ab = ab0 + b1·10 + b2·102 + ... + bn·10n = ab0·(a10)b1·(a102)b2... (a10n)bn

This product is easy, because now you can find each term by Binary Exponentiation.

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

    include<bits/stdc++.h>

    using namespace std;

    int findBigMod(string number, int div){ int carry=0; int size = number.size(); for(int i=0;i<size;i++){ carry = carry * 10 + (number[i]-'0'); carry = carry % div; } return carry;

    } int findPower(int base, int power){ int result=base; for(int i=1;i<power ; i++) result*=base; return result; } int main(){ int test; scanf("%d",&test); for(int i=1;i<=test;i++){ string base,power; cin>>base>>power; if(base== "0"){ printf("Case %d: 0\n",i); continue; } if(base=="3"){ if(power=="0"){ printf("Case %d: 1\n",i); } else if(power=="1") { printf("Case %d: 3\n",i); } else printf("Case %d: 9\n",i); continue; } if(power=="0"){ printf("Case %d: 1\n",i); continue; } int a= findBigMod(base,9); if(a==0) a=9; int b= findBigMod(power,6); b+=6;

    int ans= findPower(a,b);
    if(ans%9 == 0 ) ans=9;

    else ans= ans%9;
    printf("Case %d: %d\n",i,ans);
    base.clear();
    power.clear();
}

    return 0; }

    → Reply