http://www.codechef.com/problems/MARCHA4/
for this problem i took idea from topcoder forums http://forums.topcoder.com/?module=Thread&threadID=672262&start=0&mc=3#1228392 and from algogeeks http://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.
