Rasta and Darie

A Darie is a special circle. Numbers 1, 2, ..., n are written clockwise around this circle in order. You can stand on a number! Initially Rasta is on number 1. In each step, he jumps exactly p numbers clockwise. For example if n = 3 and he is standing on number 1:
If p = 1 then he jumps to number 2.
Or if p = 2 he jumps to number 3.
He does this until he reaches a number he's been on before (for example, if n = 3, p = 1 he stops after three jumps).
Then he writes down the numbers he had been on, as a sequence s in increasing order.
He's not a Mr.Memmory, so he can't remember this sequence. He asks you to help him by telling him the k-th number in this sequence (or -1 if size of s is less than k).

Input format

The first line of input contains an integer t, the number of testcases (1 ≤ t ≤ 10⁵).
Each testcase is given in one line, which contains three integers n, p, k (2 ≤ n ≤ 10⁶, 1 ≤ p ≤ n - 1, 1 ≤ k ≤ 10⁶).

Output format

Print the answer of each testcase in one line.

---

Sample Input

3
12 5 3
12 3 2
3 2 2

Sample Output

3
4
2

---

Time Limit: 2 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

 

For this problem you need a bit of math knowledge, after that it becomes really simple.
First let's move to 0-indexed numbering. It will make things looking simpler. Instead of 1, p+1, 2p+1,... now we have 0, p, 2p,... Let's notice that position after X moves is pX%n.
The key fact required to solve this one is that if p and n are coprime, then Darie will cover all possible values (he will make it with first n moves: pn, 2p%n, 3p%n, ... , np%n will give you a permutation of numbers 0, ..., n-1).

Let's make them coprime :) Assume we have gcd(n,p)=q. Lets denote N=n/q, P=p/q. Now we know that P and N are coprime (otherwise we can multiply q by their common divisor). Also we know that P%N, 2P%N, ... , NP%N covers all values in range 0, ..., N-1. Now move back to original values. After multiplying by q we have values 0, q, 2q, ..., (N-1)q covered. These N values are all positions which can be reached by Darie. If you are asked about position which has index higher than size of this list - answer is -1; otherwise you may find answer as (k-1)q. Don't forget to output it as (k-1)q+1, because we have 1-based numbering in original problem.
 

 

 

Code : 

 

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;

public class Test{
    static int temp;

    public static void main(String[] args) throws IOException {
        Reader reader = new Reader();
        PrintWriter out = new PrintWriter(System.out, false);
        int T = reader.nextInt();
        while (T-- > 0) {
            int n = reader.nextInt();
            int p = reader.nextInt();
            int k = reader.nextInt();
            --k;
            int q = gcd(n, p);
            if ((1L * k * q) >= n)
                out.println("-1");
            else
                out.println((1L * k * q) + 1);
        }
        out.close();
    }

    static int gcd(int c, int d) {
        int temp;
        while (d != 0) {
            temp = c % d;
            c = d;
            d = temp;
        }
        return c;
    }

    @SuppressWarnings("unused")
    private static int findGCD(int number1, int number2) {
        if (number2 == 0) {
            return number1;
        }
        return findGCD(number2, number1 % number2);
    }

    static int partition(int arr[], int l, int r) {
        int x = arr[r], i = l;
        for (int j = l; j <= r - 1; j++) {
            if (arr[j] <= x) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;
        return i;
    }

    static int test(int arr[], int l, int r, int k) {
        int pos = 0;
        if (k > 0 && k <= r - l + 1) {
            pos = partition(arr, l, r);
            if (pos - l == k - 1)
                return arr[pos];
            if (pos - l > k - 1)
                return test(arr, l, pos - 1, k);
            return test(arr, pos + 1, r, k - pos + l - 1);
        }
        return k;
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public final String readString() throws IOException {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.')
                while ((c = read()) >= '0' && c <= '9')
                    ret += (c - '0') / (div *= 10);
            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
}