# FINDMOD - Editorial

Author: Agnimandur
Tester: Danny Mittal
Editorialist: Nishank Suresh

Easy - Medium

# 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 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 y = HI - a - 1;
}
}

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