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))
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));
}
}