RPS #009 - Is $10^{2015}$ A Huge Number?

Number Theory Level 3

Find the sum of all the member of A if given a set of A which defined as $A = \{x | x = n^{10^{2015}} mod 125; n,x \in N_{0}\}$

(Note that $N_0 = \{0,1,2,3,...\}$ )

The answer is 1.

1 solution

A Steven Kusuman
Jan 27, 2015

include <stdio.h>

include <string.h>

include <algorithm>

using namespace std;

unsigned long long bin_s(unsigned long long n, unsigned long long p, unsigned long long m){

    unsigned long long t, val;

    if(p > 1){

        t = bin_s(n, p/2, m) % m;

        val = (t * t) % m;

        if(p % 2 == 1) val = (val * n) % m;

    }
    else if(p==1) val = n % m;

    else val = 1;

return val;
}

int main() {

unsigned long long a,b,c,m,t1,t2,i;

scanf("%llu",&a);

b=10;

c=2015;

m=125;

a=a%m;

for (i=0; i<c; i++){

    a=bin_s(a,b,m);

}

a=a%m;

printf("%llu\n",a);

return 0;

}

//This program i wrote is about fast exponentiation of integer, this prove for every n, if (n mod 5 != 0) then n=1; hence the answer is 1 !

RPS #009 - Is 1 0 2015 10^{2015} 1 0 2 0 1 5 A Huge Number?