As far as modular arithmetic is concerned, (x * z *z )%MOD = (x *(z *z)%MOD)%MOD = ((x%MOD)*(z%MOD)*(z%MOD))%MOD
But when you try to calculate *(x * z * z)%MOD*, the intermediate result of* (x * z * z) *overflows the integer limit and hence gives the wrong result. similarly, intermediate value of *(x%MOD) * (y%MOD) * (z%MOD)* might also overflow the integer limit hence you are getting WA. On Tuesday, October 25, 2011, Kunal Patil wrote: > 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. > -- 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>>
