Re: [algogeeks] [SPOJ] ZSUM

2011-10-25 Thread Kunal Patil 
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.comwrote:

 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-SPOJhttps://www.spoj.pl/problems/ZSUM/

 Here is my code: Let me know if you can find the problem with the code


 #includecstdio
 #define MOD 1007

 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(nk){
 u64 ans = 0;

 if(n0)
 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

Re: [algogeeks] [SPOJ] ZSUM

2011-10-25 Thread Aamir Khan 
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-SPOJhttps://www.spoj.pl/problems/ZSUM/

 Here is my code: Let me know if you can find the problem with the code


 #includecstdio
 #define MOD 1007

 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(nk){
 u64 ans = 0;

 if(n0)
 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

Re: [algogeeks] [SPOJ] ZSUM

2011-10-20 Thread Wasif Hossain 
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-SPOJhttps://www.spoj.pl/problems/ZSUM/

 Here is my code: Let me know if you can find the problem with the code


 #includecstdio
 #define MOD 1007

 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(nk){
 u64 ans = 0;

 if(n0)
 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.

[algogeeks] [SPOJ] ZSUM

2011-10-05 Thread hashd 
I'm getting WA on the question : ZSUM-SPOJhttps://www.spoj.pl/problems/ZSUM/

Here is my code: Let me know if you can find the problem with the code


#includecstdio
#define MOD 1007

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(nk){
u64 ans = 0;

if(n0)
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.