del

Edited by author 20.02.2024 17:47

?

I got wrong answer beacuse of test 6
Someone please explain what is test 6
Program in C




#include <stdio.h>
#include <math.h>

int main()
{
    long int n,m,y;
    int x,cont=0,aux1;

scanf("%d %d %d",&n,&m,&y);



for (int i = 0; i <=m-1 ; ++i)
{

    aux1=pow(i,n);

    if (aux1%m == y)
    {
        printf("%d ",i);
cont++;

    }


}
if (cont == 0)
{
    printf("-1\n");
}



    return 0;
}

Edited by author 13.10.2020 05:27

Use Bigmod Algorithm

Edited by author 26.10.2013 22:11

Because of p*=(i%m) was WA. When I wrote p=(p*i)%m instead of p*=(i%m) then  I got AC
Why???

class Program
    {
        public static void Mod(int N, int M, int Y)
        {

            int f = 0, t = -1;
            for (int i = 0; i < M; i++)
            {
                int X = i;
                long y = X;
                for (int j = 2; j < N + 1; j++)
                {
                    y = y * X;
                    y = y % M;
                }
                if (y == Y)
                {
                    if (f > 0)
                        Console.Write($" ");
                    Console.Write($"{X}");
                    f++;
                }
            }
            if (f == 0)
                Console.Write($"{t}");
            Console.WriteLine();
        }
    }

Edited by author 17.09.2019 02:10

This is my solution O(M log N)

#include <bits/stdc++.h>
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define N 100500
#define oo ll(1e16)
#define P pair < int, int >
#define PP pair < pair < int, int >, int >
#define F first
#define S second
#define pb push_back
#define el endl
#define base ll(1e9 + 7)
using namespace std;
typedef long long ll;
typedef long double ld;
int n, m, y;
bool o;
int bin(int x, int st) {
    int res = 1;
    for(; st > 0;) {
        if (st & 1) res = (res * x) % m;
        x = (x * x) % m;
        st >>= 1;
    }
    return res;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> y;
    o = 0;
    for (int i = 1; i < m; i++) {
        int cur = bin(i, n);
        if (cur == y) cout << i << ' ', o = 1;
    }
    if (!o) cout << -1;
}

The problem limits are too small.
You can get ac with the O(N^2) algorithm which is VERY
straightforward. The limit should force you to use the O
(log N) algorithm to compute X^N (%M)

#include<iostream>
#include<cmath>
using namespace std;

int func(int k, int n, int m)
{
    if(n == 0)
        return 1;
    else
        return func(k, n-1, m)*k%m;
}

int main()
{
    int n, m, y, x, i = 0;
    int b;
    bool flag = true;
    cin >> n >> m >> y;
    if((n >0 && n < 999) && (m > 1 && m < 999)  && (0 < y && < 999))
    {
    while(i < m)
    {
        x = func(n, i, m);
        if(x == y)
        {
                cout << i << ' ';
                flag = false;
        }
        i++;
    }
    if(flag)
        cout << "-1";
}
else
cout << "-1";

    return 0;
}

Edited by author 08.02.2018 02:25

Edited by author 08.02.2018 02:27

Here is my java code :


import java.util.Scanner;
public class Example{
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        int number1,number2,number3;
        int [] array;
        int position=0;
        boolean check=false;
        int sth;
        number1=in.nextInt();
        number2=in.nextInt();
        number3=in.nextInt();
        array = new int[number2];
        for(int i=0;i<=number2-1;i++){
            sth=(int)Math.pow(i,number1);
            if((sth-number3)%number2==0){
                array[position]=i;
                position++;
                check=true;
            }else if(i==number2-1 && check==false){
                System.out.println(-1);
                System.exit(0);
            }

        }
        for(int p=0;p<position-1;p++){
            for(int j=p+1;j<position;j++){
                if(array[p]>array[j]){
                    int t=array[p];
                    array[p]=array[j];
                    array[j]=t;
                }
            }
        }
        for(int i=0;i<position;i++){
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

I get an error on test#3 .
And on my C++ solution i get an error on test#6.



#include<iostream>
#include<cmath>
using namespace std;
int main(void){
unsigned short int N,M,Y;
cin>>N>>M>>Y;
unsigned short int X[M];
unsigned short int position=0;
bool some_check=false;
int sth;
for(int i=0;i<=M-1;i++){
    sth=pow(i,N);
    if((sth-Y)%M==0){
        X[position]=i;
        position++;
        some_check=true;
    }
    else if(i==M-1 && some_check==false){
        cout<<-1<<endl;
        return 0;
    }
}
for(unsigned short int i=0;i<position-1;i++){
    for(unsigned short int j=i+1;j<position;j++){
        if(X[i]>X[j]){
            swap(X[i],X[j]);
        }
    }
}
for(unsigned short int i=0;i<position;i++){
    cout<<X[i]<<" ";
}
cout<<endl;
return 0;
}


Please,any ideas ???

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.

This is the right solution
Sorry for my english

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.

#include<iostream>
using namespace std;
int main()
{
    int N, M, Y;
    while (cin >> N >> M >> Y)
    {
        int f = 0,t=-1;
        for (int i = 0; i < M; i++)
        {
            int x = i;
            long long y = x;
            for (int j = 2; j < N + 1; j++)
            {
                y *= x;
                y %= M;
            }
            if (y== Y)
            {
                if (f > 0)
                    cout << ' ';
                cout << x ;
                f ++;
            }
        }
        if (f == 0)
            cout << t;
        cout << endl;
    }
    return 0;
}

why it can get accept,but this one get WA

#include<iostream>
using namespace std;
int main()
{
    int N, M, Y;
    while (cin >> N >> M >> Y)
    {
        int f = 0,t=-1;
        for (int i = 0; i < M; i++)
        {
            int x = i;
            long long y = x;
            for (int j = 2; j < N + 1; j++)
            {
                y *= x;
            }
            if (y%M== Y)
            {
                if (f > 0)
                    cout << ' ';
                cout << x ;
                f ++;
            }
        }
        if (f == 0)
            cout << t;
        cout << endl;
    }
    return 0;
}

var
   m, n, b, y, k, x: integer;

function St(x, n: integer): integer;
var
   i, f: integer;
begin
   f := 1;
   for i := 1 to n do
      f := f * x;
   St := f;
end;

begin
   readln(n, m, y);
   for x := 0 to m - 1 do
   begin
      b := st(x,n);
      if (b mod m) = y then
      begin
         write(x,' ');
         k := k + 1;
      end;
   end;
   if k = 0 then
      writeln(-1);
end.

I take WR!!! I don't know what s wrong!!!
---------------------------------MY PROGRAM-------------------------
var N,M,Y:longint;
    a:array[1..15]of byte;
    b:array[1..15]of longint;
    d:array[1..1000]of integer;
    h,x,l:integer;
    i,j,s:longint;
begin
  assign(input,'1110.dat');
  reset(input);
  readln(N,M,Y);
  x:=N;
  for i:=1 to 15 do
  begin
    a[i]:=x mod 2;
    x:=x div 2;
    if x = 0 then break;
  end;
  l:=i;
  for i:=0 to M-1 do
  begin
    b[1]:=i;
    for j:=2 to l do
    begin
      b[j]:=(b[j-1]*b[j-1]) mod M;
    end;
    s:=1;
    for j:=1 to l do if a[j]=1 then
    begin
      s:=(s*b[j]) mod M;
    end;
    if s = Y then
    begin
      inc(h);
      d[h]:=i;
    end;
  end;
  for i:=1 to h-1 do write(d[i],' ');
  if h<>0 then writeln(d[h]);
end.

del

Edited by author 06.01.2015 21:37

done...

Edited by author 30.11.2014 01:32

Edited by author 30.11.2014 01:32

In Pascal I have AC, but in Java - WA, why??

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int N, M, Y = 0;
        boolean check = false;

        N = in.nextShort();
        M = in.nextShort();
        Y = in.nextShort();

        double p;

        if ( ((0<N) && (N<999)) && ((1<M) && (M<999)) && ((0<Y) && (Y<999)) ) {
            for (int X=0; X<=M-1; ++X) {
                p = ((Math.pow(X,N)) % M);
                if (p == Y) {
                    if (X != (M-2)) {
                        out.print(X + " ");
                    } else {
                        out.print(X);
                    }
                    check = true;
                }
            }
        }

        if (!check) {
            out.print("-1");
        }

        out.flush();
    }
}

A couple of tests that I obtained from my working program:

998 999 972
48 63 159 174 270 285 381 396 492 507 603 618 714 729 825 840 936 951

998 999 900
-1

Scroll down for hint.
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v

Hint:  (A*B) MOD C = ((A MOD C) * B) MOD C

Edited by author 13.10.2011 19:15

Edited by author 13.10.2011 19:16