what is the difference between this code and that code, still get wrong
Posted by
VNeo 16 Jul 2017 06:34
i got WA#6 when i use this code
#include <iostream>
#include <cmath>
using namespace std;
long int n,m,y,p,q,r[999];
int main(){
cin>>n>>m>>y;
for (int i=0;i<m;i++){
if (lround(pow(i,n)) % m==y){
q++;
r[q]=i;
}
}
if (q==0){
cout<<"-1";
}
else {
for (int i=1;i<=q;i++){
cout<<r[i]<<' ';
}
}
}
but when i use neighbored code which is already acc, and tested some test case between them, it give me same results. whats probably wrong in my code
by the way, the neighbored code is pascal language, but the point is, i just used that for test case.
Re: what is the difference between this code and that code, still get wrong
Posted by
VNeo 16 Jul 2017 06:35
oh , i forgot. The neighbored code is this
var ans: array[1..1000] of longint;
n,m,y,q,i: longint;
function BinPow(x,y: longint): longint;
begin
if y=1 then BinPow:=x
else if y mod 2=0 then BinPow:=sqr(BinPow(x,y div 2)) mod M
else BinPow:=(sqr(BinPow(x,y div 2))*x) mod M;
end;
begin
readln(n,m,y);
q:=0;
for i:=0 to m-1 do
begin
if BinPow(i,n)=y then
begin
inc(q);
ans[q]:=i;
end;
end;
for i:=1 to q do
write(ans[i],' ');
if q=0 then writeln(-1);
end.
netman from timus judge, sorry for copied your code.
Re: what is the difference between this code and that code, still get wrong
Look at the limitations.
You can have X^N=998^998. That is 9,98e1000.
Look at fundamental data types range. double is something like not greater (-1e309;1e309) with 15 digits after point . That is much smaller than you need. So, in function pow there is an overflow. That means double LOSES PRECISION. And if actually X^N mod M == Y for some big X^N them your program can't see it. Because last digits of X^N are lost due to an overflow.
And in netman's code, there is such a function, that keeps ONLY the last digits.
Re: what is the difference between this code and that code, still get wrong
So, the main difference is.
Your code keeps MOST significant digits.
netman's code keeps LEAST significant digits.
More precisely, netman's code keeps last approximately log10(M) +1 digits.
Re: what is the difference between this code and that code, still get wrong
That is, if the number is say
12345...{lot of digits}... 6789
Then your code keeps 1234 as digits and keeps additional information only about HOW MANY digits are before 1234.
And netman's code keeps only digits 6789.
Re: what is the difference between this code and that code, still get wrong
Posted by
VNeo 16 Jul 2017 18:09
so, what i've gonna do?. I still cant find the solution.
is there are any function like pow, but can keep LEAST significants digits like you said before?
Re: what is the difference between this code and that code, still get wrong
Posted by
VNeo 16 Jul 2017 18:25
still get WA#6, after change lround into llround. but why?, llround is the function that round nearest decimal into long long integer. it much more greater than lround.
Re: what is the difference between this code and that code, still get wrong
int pow(int X, int N, int M) {
if(N<1)
return 1;
int res=pow(X, N>>1, M);
res=(res*res)%M;
if(N&1)
return (X*res)%M;
return res;
}
Re: what is the difference between this code and that code, still get wrong
What is maximal long long? something like 1e20.
It is so SMALL against 998^998.
Re: what is the difference between this code and that code, still get wrong
I got AC right now with this power function.
Re: what is the difference between this code and that code, still get wrong
Hurra, 0.001 sec!