use log properties (mantissa) to calculate the first k digit of n^n. i am giving u working code, which gives answer in answer variable,
double dummy =0; f= (double)pow(10,modf((double)n*log10((double)n),&dummy)+k-1); answer=(int)f; On Oct 4, 9:03 pm, navin <navin.myhr...@gmail.com> wrote: > http://www.codechef.com/problems/MARCHA4/ > > for this problem i took idea from topcoder > forumshttp://forums.topcoder.com/?module=Thread&threadID=672262&start=0&mc=... > > and from > algogeekshttp://www.mail-archive.com/algogeeks@googlegroups.com/msg06159.html > > sorry that it was already discussed. > my problem is it gives me precision error. > > input: > 11 > 4 2 > 9 3 > 999 5 > 457474575 9 > 1000000000 9 > 999999999 9 > 19 9 > 28 8 > 27 1 > 19423474 8 > 19423474 9 > > output: > 25 56 > 387 489 > 36806 98999 > 278661176 380859375 > 100000000 000000000 > 367880063 999999999 > 197841965 589123979 > 33145523 05812736 > 4 3 > 16307491 26110976 > 163074912 826110976 > > myouput > 25 56 > 387 489 > 36806 98999 > 278660870 380859375 > 100000000 000000000 > 367880063 999999999 > 197841965 589123979 > 33145523 05812736 > 4 3 > 16307490 26110976 > 163074908 826110976 > > test cases taken from comments. > > see for the last 2 test case two digits are varying. > I dont know how to correct the precision error while taking log10. > > can you help me. > > here follows my code. > > #include<iostream> > #include<vector> > #include<cmath> > #include<cstring> > using namespace std; > > long long modular_exponential(long long a, long long k, long long mod) > { > if ( k == 1 ) > return a; > else > { > if ( k%2 == 1 ) > { > return a * modular_exponential( a , k-1 , mod ) % > mod ; > } > else > { > long long val = modular_exponential( a , k/2 , mod ) % > mod ; > return (val*val) % mod; > } > }} > > main() > { > int t; > cin >> t; > while ( t-- ) > { > > long long n; > int k; > > cin >> n >> k; > > double v = n*log10(n); > double dummy; > //cout << "v = " << v << endl ; > double ff = modf(v,&dummy); > //cout << "ff = " << ff << endl ; > double val = pow(10.0,ff); > long long mod = 1; > for(int i = 0 ; i < k-1 ; i ++ ) > { > val = val*10; > mod = mod*10; > } > mod = mod*10; > > cout <<(int) val << " "; > > long long vv = modular_exponential( n , n , mod ) ; > > if ( vv == 0 ) > { > for(int i = 0 ; i < k ; i ++ ) > { > cout <<"0"; > } > > } > else > { > char str[100]; > sprintf(str,"%lld",vv); > > int l = strlen(str); > > if ( l == k ) > cout << vv; > else > { > int diff = k-l; > for(int i = 0 ; i < diff ; i ++ ) > cout << "0" ; > cout << vv ; > } > } > cout << endl ; > } > > } -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
