FINDMOD - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Agnimandur
Tester: Danny Mittal
Editorialist: Nishank Suresh

DIFFICULTY:

Easy - Medium

PREREQUISITES:

Intuition about modulo arithmetic

PROBLEM:

There is a hidden number N. You are allowed to ask upto 2 queries, each of which requires you to provide a number X following which you are told X \mod N. Find N.

EXPLANATION:

Let’s analyze the results of a single query.

  • If X < N, X\mod N = X, so in this case the judge will just return X. The only information this gives us is that X < N \leq 10^{18}, which doesn’t help much in narrowing anything down at all.
  • If X \geq N, suppose the judge returns Y. Then, Y is the remainder when X is divided by N - in other words, N divides X - Y (which, in this case, is a positive integer).

The above observations tell us that it’s useless to query for small X, so let’s focus on the second part instead.

Solution 1 (Editorialist)

Suppose our two queries are X_1 and X_2, with results Y_1 and Y_2 respectively. We then know two multiples of N, namely X_1 - Y_1 and X_2 - Y_2. This by itself is not enough to find N, which could be any common factor of the two.

However, it is possible to query smartly such that N turns out to be the greatest common divisor of X_1 - Y_1 and X_2 - Y_2.

As noted, querying for small X is bad, so let’s have X_1 = 10^{18} with the answer to this query being Y_1.

Now consider what happens when we query for X_2 = X_1 - Y_1 - 1, with result Y_2.

We know that N divides both Z_1 = X_1 - Y_1 and Z_2 = X_2 - Y_2.
Let d = \gcd(Z_1, Z_2). It turns out that N = d, so after asking these queries it suffices to find and print d.

Proof

Clearly N \leq d because N divides both Z_1 and Z_2, hence it divides their gcd.

Now, consider the number X_1 - Y_1 - 1 - (N-1) = X_1 - Y_1 - N.
We know that N divides X_1 - Y_1, so N divides X_1 - Y_1 - N. However, Y_2 is the smallest number that can be subtracted from X_1 - Y_1 - 1 to make it divisible by N, hence we must have N-1 \geq Y_2.

However, we also have (using the property \gcd(a, b) = \gcd(a, b-a))

d = \gcd(X_1 - Y_1, X_2 - Y_2) = \gcd(X_1 - Y_1, X_1 - Y_1 - 1 - Y_2) = \gcd(X_1 - Y_1, Y_2 + 1)

which means that d\leq Y_2 + 1, or d-1\leq Y_2.

Putting our inequalities together, N-1\geq Y_2\geq d-1 \implies N\geq d.
So, we have N = d, as required.

Solution 2 (Tester)

Let X_1 be a prime larger than the largest possible N - for example, 10^{18} + 3.
Let Y_1 = query(X_1).
Now query for X_2 = X_1 - 2Y_1, let the result be Y_2.
The required answer is then Y_1 + Y_2.

First, note that X_1 - 2Y_1 is indeed positive, so X_2 is a valid query (proof left as an exercise to the reader :)).

Now, note that X_1 - 2Y_1 \pmod N = X_1 - Y_1 - Y_1 \pmod N = -Y_1 \pmod N, because X_1 - Y_1 = 0 \pmod N.

Thus, Y_2 will always end up being N - Y_1 \pmod N, because Y_1 < N and N-Y_1 < N.

As long as Y_1 \neq 0, it’s easy to see that this solution works. When can we have Y_1 = 0?
Since, X_1 was chosen to be a large prime, almost never!

In fact, it is only possible for Y_1 to equal 0 if N = 1.
So, if the answer to our first query is 0, we know the answer is 1; else, we find Y_2 as described above and then have N = Y_1 + Y_2.

TIME COMPLEXITY:

\mathcal{O}(1) per test.

CODE:

Setter (C++)
#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define si set<int>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define vl vector<long long>
#define pii pair<int, int>
#define pll pair<ll,ll>
#define add push_back
#define REP(i,a) for (int i = 0; i < (a); i++)
using namespace std;
 
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
const int INF = 1005000000; 
const ll MOD = 1000000007LL;
//const ll MOD = 998244353LL;
 
int ni() {
    int x; cin >> x;
    return x;
}
 
ll nl() {
    ll x; cin >> x;
    return x;
}
 
double nd() {
    double x; cin >> x;
    return x;
}
 
string next() {
    string x; cin >> x;
    return x;
}

ll query(ll X) {
    cout << "? " << X << endl;
    ll result = nl();
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T = ni();
    for (int i = 1; i <= T; i++) {
        ll X1 = 1e18;
        ll Y1 = query(X1);
    
        ll X2 = X1-Y1-1;
        ll N = query(X2)+1;
    
        cout << "! " << N << endl;
    }
}
Tester (Kotlin)
import java.io.BufferedInputStream
import java.lang.IllegalArgumentException

const val LIMIT = 1000000000000000000L

fun main(omkar: Array<String>) {
    val jin = FastScanner()
    repeat(jin.nextInt(100)) {
        fun query(x: Long): Long {
            println("? $x")
            val res = jin.nextLong(true)
            if (res !in 0L until LIMIT) {
                throw IllegalArgumentException("query result $res not in range 0 until 10^18")
            }
            return res
        }
        val x1 = LIMIT + 3L
        val y1 = query(x1)
        if (y1 == 0L) {
            println("! 1")
        } else {
            val z1 = x1 - y1
            val x2 = z1 - y1
            val y2 = query(x2)
            val answer = y1 + y2
            println("! $answer")
        }
    }
}

class FastScanner {
    private val BS = 1 shl 16
    private val NC = 0.toChar()
    private val buf = ByteArray(BS)
    private var bId = 0
    private var size = 0
    private var c = NC
    private var `in`: BufferedInputStream? = null

    constructor() {
        `in` = BufferedInputStream(System.`in`, BS)
    }

    private val char: Char
        private get() {
            while (bId == size) {
                size = try {
                    `in`!!.read(buf)
                } catch (e: Exception) {
                    return NC
                }
                if (size == -1) return NC
                bId = 0
            }
            return buf[bId++].toChar()
        }

    fun assureInputDone() {
        if (char != NC) {
            throw IllegalArgumentException("excessive input")
        }
    }

    fun nextInt(endsLine: Boolean): Int {
        var neg = false
        c = char
        if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
            throw IllegalArgumentException("found character other than digit, negative sign, space, and newline")
        }
        if (c == '-') {
            neg = true
            c = char
        }
        var res = 0
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0')
            c = char
        }
        if (endsLine) {
            if (c != '\n') {
                throw IllegalArgumentException("found character other than newline")
            }
        } else {
            if (c != ' ') {
                throw IllegalArgumentException("found character other than space")
            }
        }
        return if (neg) -res else res
    }

    fun nextInt(from: Int, to: Int, endsLine: Boolean = true): Int {
        val res = nextInt(endsLine)
        if (res !in from..to) {
            throw IllegalArgumentException("$res not in range $from..$to")
        }
        return res
    }

    fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)

    fun nextLong(endsLine: Boolean): Long {
        var neg = false
        c = char
        if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
            throw IllegalArgumentException("found character other than digit, negative sign, space, and newline, character code = ${c.toInt()}")
        }
        if (c == '-') {
            neg = true
            c = char
        }
        var res = 0L
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0').toLong()
            c = char
        }
        if (endsLine) {
            if (c != '\n') {
                throw IllegalArgumentException("found character other than newline")
            }
        } else {
            if (c != ' ') {
                throw IllegalArgumentException("found character other than space")
            }
        }
        return if (neg) -res else res
    }
}
Editorialist (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    
    const ll HI = 1e18;
    auto ask = [&] (ll x) {
        cout << "? " << x << endl;
        ll in; cin >> in;
        return in;
    };
    auto answer = [] (ll x) {
        cout << "! " << x << endl;
    };
    
    int t; cin >> t;
    while (t--) {
        ll a = ask(HI);
        ll y = HI - a - 1;
        ll b = ask(y);
        answer(gcd(HI-a, y-b));
    }
}
2 Likes

You need not even apply gcd

Lets say x1 is the first guess and judge returns y1 then, (x1-y1-1)%N will give us N-1 as x1-y1 is divisible by N
so we can make second guess as (x1-y1-1), lets say the judge outputs y2. We can just print y2+1 as the answer

By the way why is this solution timing out: Solution: 53083010 | CodeChef
but not: Solution: 53052820 | CodeChef

both implement the above approach that I mentioned

5 Likes

The other user is flushing output using endl.

1 Like

Thanks! adding flush did get the solution accepted. Never had to do it. But I guess this is required for interactive problems on codechef.

1 Like

I did with 1e18+1 and got AC. Lol

An approach worth mentioning :
Query X = 1e18 + 5 (Any number greater than the largest possible value for N).
Lets Y be the result of the query.
Query X - (Y+1) . Result of the query be ANS .
N would be ANS+1.

Intuition : If we decrease X by 1, modulo will also decrease also by 1 up until 0. After modulo becomes 0 if we decrease X by 1, modulo will then become N-1.

10 Likes

In the Editorialist’s solution, we don’t need to apply gcd(Z1, Z2). Just Z1 - Z2 will give the answer.

Best explanation