Can you tell why (x * z * z) % MOD is different from (x * ( (z*z)%MOD) ) % MOD
Again why ((x%MOD)*(z%MOD)*(z%MOD))%MOD is giving WA ???? I thought of a simple examples like (100* 53*72) % 90 --> ((90+10)*53*72) % 90 --> (10*53*72)% 90 which is same as (100%90 * 53%90 * 72%90) % 90 Another example (100*91*92)%90 --> ( (90+10)*(90+1)*(90+2) ) % 90 --> 10 * 1 * 2 which is again same as (100%90 * 91%90 * 92%90) % 90 Are results different because of range overflow in case of bigger z ??? I'm weak at modular mathematics [?] So please help !! On Thu, Oct 20, 2011 at 11:48 AM, Wasif Hossain <wasifhossain....@gmail.com>wrote: > Just a MINOR change. > please change the RED line(I've marked it below) in your code by the > following line: > *return (x*((z*z)%MOD))%MOD;* > and enjoy an *ACCEPTED *verdict.* > * > > *Wasif Hossain** > * > B.Sc. Student of Final Semester, > Computer Science and Engineering(CSE), > Bangladesh University of Engineering and Technology(BUET), > Dhaka-1000 > Bangladesh. > > On Thu, Oct 6, 2011 at 1:13 AM, hashd <kirandandupr...@gmail.com> wrote: > >> I'm getting WA on the question : >> ZSUM-SPOJ<https://www.spoj.pl/problems/ZSUM/> >> >> Here is my code: <Let me know if you can find the problem with the code> >> >> >> #include<cstdio> >> #define MOD 10000007 >> >> typedef unsigned long long u64; >> using namespace std; >> >> u64 modExp(u64 x, u64 y){ >> if(x==0) >> return 0; >> >> if(y==0) >> return 1; >> >> u64 z = modExp(x,y/2); >> >> if(y%2==0) >> return (z*z)%MOD; >> else >> *return (x*z*z)%MOD;* >> } >> >> int main(){ >> u64 n, k; scanf("%llu%llu",&n,&k); >> while(n&&k){ >> u64 ans = 0; >> >> if(n>0) >> ans = (2*modExp(n-1,k) + modExp(n,k) + 2*modExp(n-1,n-1) + >> modExp(n,n))%MOD; >> >> printf("%llu\n",ans); >> scanf("%llu%llu",&n,&k); >> } >> >> return 0; >> } >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/p6j7nmaEUb4J. >> To post to this group, send email to algogeeks@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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
<<33D.gif>>