ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1110. Power

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
Posted by Mahilewets 16 Jul 2017 09:03
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
Posted by Mahilewets 16 Jul 2017 09:48
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
Posted by Mahilewets 16 Jul 2017 09:51
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
Posted by Mahilewets 16 Jul 2017 18:28
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
Posted by Mahilewets 16 Jul 2017 18:29
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
Posted by Mahilewets 16 Jul 2017 18:30
I got AC right now with this power function.
Re: what is the difference between this code and that code, still get wrong
Posted by Mahilewets 16 Jul 2017 18:32
Hurra,  0.001 sec!