import java.math.BigInteger;


public class BSGS {

	


	private static int d;
	//private static long[] tab;
    static BigInteger ze=new BigInteger("0");

	/**
	 * @param args
	 */
	
	public static int compare(BigInteger t, BigInteger[] tab) {
		int i=0;
		while (i < tab.length) {
			if (t==tab[i]) return(i);
			i++;
		}
	return(-1);
		
	}
	
	public static BigInteger bigIntSqRootCeil(BigInteger x)
	        throws IllegalArgumentException {
	    if (x.compareTo(BigInteger.ZERO) < 0) {
	        throw new IllegalArgumentException("Negative argument.");
	    }
	    // square roots of 0 and 1 are trivial and
	    // y == 0 will cause a divide-by-zero exception
	    if (x == BigInteger.ZERO || x == BigInteger.ONE) {
	        return x;
	    } // end if
	    BigInteger two = BigInteger.valueOf(2L);
	    BigInteger y;
	    // starting with y = x / 2 avoids magnitude issues with x squared
	    for (y = x.divide(two);
	            y.compareTo(x.divide(y)) > 0;
	            y = ((x.divide(y)).add(y)).divide(two));
	    if (x.compareTo(y.multiply(y)) == 0) {
	        return y;
	    } else {
	        return y.add(BigInteger.ONE);
	    }
	} // end bigIntSqRootCeil
	
	// quatre arguments sont attendus
	// 1) un nombre premier p
	// 2) un élément a de (Z/pZ)*
	// 3) l'ordre q de a
	// 4) un élément h de (Z/pZ)* dont on cherche n tel que h=a^n
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		if (args.length < 4) {
            System.out.println("Pas assez d'arguments");
            System.exit(0);
        }
		BigInteger p=new BigInteger(args[0]);
		BigInteger a=new BigInteger(args[1]);
		BigInteger q=new BigInteger(args[2]);
		BigInteger h=new BigInteger(args[3]);
		BigInteger dd=bigIntSqRootCeil(q);
		int d=dd.intValue();	
		BigInteger[] tab= new BigInteger[d];
		for (BigInteger i = ze; i.compareTo(dd)==-1; i=i.add(BigInteger.ONE)) { // Baby Steps
			BigInteger ii=a.modPow(i,p);
			ii=ii.modInverse(p);
			if (ii.compareTo(ze)==-1) ii=ii.add(p);
			tab[i.intValue()]=ii.multiply(h).mod(p);
			//System.out.print(i+" ");
			//System.out.println(tab[i]);
		}
		BigInteger t= new BigInteger("1");
		int e=0;
		BigInteger per=a.modPow(dd, p);
		while (compare(t,tab)==-1 & e < d) { // Giant Steps
		   t=t.multiply(per).mod(p);
		   e++;
		   }
		if (e==d) System.out.println("Pas de solution");
		else {long n= compare(t,tab)+d*(e-1);
		     System.out.println("l'entier n cherché est "+n);
		     }
	}

}