# PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

Setter : Bohdan Pastuschak

Tester : Alipasha Montaseri / Kasra Mazaheri

Editorialist : Anand Jaisingh

Easy Medium

# PREREQUISITES :

Prime Factorization, Modular Arithmetic, Chinese remainder theorem.

# PROBLEM :

Chef has a hidden prime P. You can ask at most 2 queries in which you give the chef an integer x, and chef replies with x^2 \hspace{0.2cm} Mod \hspace{0.2cm} P . You need to guess P successfully after these queries.

# QUICK EXPLANATION

We can first find some square free number Z that is a multiple of P, and then find a number Q, such that the residue of Q^2 is pair-wise distinct Modulo all primes of the number Z. In such a case, we can then easily recover P, by inquiring Q^2 Modulo P.

# EXPLANATION :

The approach to solve this problem is as follows :

We need to pick a single integer K, such that K^2 \ge P . Let’s pick any number K large enough so that K^2 is always \ge any given P. For example, we could pick 10^5, as (10^5)^{2}=10^{10} \ge 10^{9}=Max(P). This number can be any integer as long as it follows the condition above. Now, we ask the first query to chef using the number K.

The information that is known to us is K^2 and K^2 \mod P . Obviously, K^2-(K^2 \mod P ) \equiv 0 \mod P . Now, let Y = K^2-(K^2 \mod P)

We know that Y is a multiple of P, and the number P is a prime, so P is a prime factor of Y. Let’s reduce Y to it’s square-free form, i.e. the product of all distinct primes Y was divisible by, since the power of primes is going to be irrelevant from here on. Let’s call the number so obtained Z.

For example, if the initial prime factorization of Y was \prod_{i=1}^{m} p_i^{e_i}, then we let Z=\prod_{i=1}^{m} p_i .

If Z= \prod_{i=1}^{m} p_i , and each p_i is prime, m \ge 1 , then, if we can find a single integer Q , such that Q^2 \hspace{0.2cm} Mod \hspace{0.2cm} p_i is pairwise distinct \forall i , then we can uniquely identify the prime P, by asking the second query as Q to chef. ( As only one of the primes p_i uniquely corresponds to chef’s reply ).

Main Claim :

We can find fast a number Q such that Q^2 \hspace{0.2cm} Mod \hspace{0.2cm} p_i is pairwise distinct, regardless of the prime factorization of the number Z. Let the prime factorization of Z consist of the primes [p_1,p_2....p_m] in increasing order. Then, we can find the number Q in O(M^2 + M \cdot \log (P)) time.

Sub Claim:

For an odd prime P, there are ((P-1)/2)+1 distinct quadratic residues Modulo P. (A quadratic residue is a number that corresponds to i^2 \mod P for some 0 \le i \le P ), and these ((P-1)/2)+1 numbers are 0^2 \mod P , 1^2 \mod P ,.... ((P-1)/2)^2 \mod P .

Proof of Sub Claim :

Firstly, 0^2 \equiv 0 \mod P . Now, for each number i > 0 , if it is a quadratic residue Modulo P, then it has exactly 2 square roots Modulo P. If one of them is j, then the other is P-j. So, as i goes from 1 to (P-1)/2, we know each of these quadratic residue is distinct ( since if j,k \le (P-1)/2 and j^2 \mod P \equiv k^2 \mod P, then we have, then this contradicts the original statement that each quadratic residue has exactly 2 square roots Modulo P.

Also, it’s obvious that if 0 < i < P , then i^2 \mod P \not\equiv 0 , since i is co-prime to P.

This completes the proof that for an odd prime P, each number from 0 to (P-1)/2 generates a distinct quadratic residue Modulo P.

Proof of Main Claim :

Now, we generate the number Q using the following operations :

Initially let idx=1, and let the set S and vector V be empty.

1. Start iterating the variable i from 0 ( incrementally), and keep doing so until we find i, such that i^2 \mod p[idx] \not\in S .
2. Add i^2 \mod p[idx] to set S, and and i to vector V. Now, increment idx. If idx > m , then stop, else go to step 1.

When we are finding a number i such that i^2 \mod P \not\in S , then we are guaranteed to find such a number in a maximum of idx steps, since each i generates a distinct quadratic residue Modulo p[idx] ( remember the proof above ), and the size of set S is exactly idx-1.

This holds because the position idx a prime P can take is always \le \frac{P-1}{2}+1 for any prime P.

Now, Q is such a number that Q \equiv v[j] \mod p[j], 1 \le j \le m . (Our vector is 1 indexed ). We can easily build such a number using the Chinese remainder theorem in O(M \log (P)) time.

Here, M can attain a maximum value of 10, since any number Z \le 10^{10} can have a maximum of 10 distinct prime factors. So, such a complexity is quite good enough to get a full score.

You can learn about the Chinese Remainder Theorem using this wonderful tutorial

Also, most solutions, including the setter and tester solutions, find the number Q by iterating over some large range like from [Z-1,min(0,Z-10^5)], and checking if some number in the range satisfies what we want, or by just iterating indefinitely, until we find the first such needed number.

It seems, the probability of finding such a number in a big enough range is very high, and such solutions are good enough to pass all tests.

However, the correctness / time complexity of such solutions is too hard to prove, and hence, I present an approach in the editorial, that has a proof, and does not leave any doubts in one’s mind.

Your comments are welcome ! Did any body use the approach described in the editorial during the contest ?

# COMPLEXITY ANALYSIS :

Time Complexity : O(\sqrt{P}+M^2 + M \cdot log(P))

Space Complexity: O(1)

# SOLUTION LINKS :

Setter
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;

int separator(VI& a)
{
for(int n = 1; ; ++n)
{
set<int> r;
for(auto i: a)
r.insert(n * n % i);
if (SZ(r) == SZ(a))
return n;
}
}

const int N = 193;
const int M = N * N + 1;
VI classes[M];
bool is_composite[M];

{
cout << "1 " << x << endl;
fflush(stdout);
cin >> x;
return x;
}

int solve_big_prime()
{
int x = 31623;
int v = x * x - ask(x);
assert(v);

FOR(i, 2, M)
while (v % i == 0)
v /= i;
return v;
}

int solve_small_prime(int x)
{
int g = separator(classes[x]);
int v = ask(g);

for(auto i: classes[x])
if (g * g % i == v)
return i;
assert(0);
}

void solve()
{
int ans = -1;
int x = ask(N);
if (x == N * N)
ans = solve_big_prime();
else
ans = solve_small_prime(x);

cout << "2 " << ans << endl;
fflush(stdout);

string response;
cin >> response;
assert(response == "Yes");
}

int main()
{
FOR(i, 2, M)
if (!is_composite[i])
{
classes[N * N % i].PB(i);
for(LL j = i *(LL) i; j < M; j += i)
is_composite[j] = 1;
}

int tc;
cin >> tc;
while(tc--)
solve();
return 0;
}

Tester
/*
Take me to church
I'll worship like a dog at the shrine of your lies
I'll tell you my sins and you can sharpen your knife
Offer me that deathless death
Good God, let me give you my life
*/
#include<bits/stdc++.h>
using namespace std;
vector < int > Factorize(int n)
{
vector < int > P;
for (int i = 2; i * i <= n; i ++)
if (n % i == 0)
{
P.push_back(i);
while (n % i == 0)
n /= i;
}
if (n > 1)
P.push_back(n);
return (P);
}
int main()
{
int A = 43222, B = 40009;
int q; scanf("%d", &q);
for (; q; q --)
{
char ss[7];
int r1, r2;
printf("1 %d\n", A);
fflush(stdout);
scanf("%d", &r1);
if (r1 == 0)
{
printf("1 2\n");
fflush(stdout);
scanf("%d", &r2);
if (r2 == 0)
printf("2 2\n");
else
printf("2 %d\n", A / 2);
fflush(stdout);
scanf("%s", ss);
//assert(ss[0] == 'Y');
continue;
}
printf("1 %d\n", B);
fflush(stdout);
scanf("%d", &r2);
if (r2 == 0)
{
printf("2 %d\n", B);
fflush(stdout);
scanf("%s", ss);
//assert(ss[0] == 'Y');
continue;
}
vector < int > P, Q;
P = Factorize(A * A - r1);
Q = Factorize(B * B - r2);
map < int , int > MP;
for (int p : P)
if (p > r1 && p > r2)
MP[p] = 1;
for (int p : Q)
if (p > r1 && p > r2 && MP[p])
{
printf("2 %d\n", p);
fflush(stdout);
scanf("%s", ss);
//assert(ss[0] == 'Y');
break;
}
}
return 0;
}

Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh

#include<bits/stdc++.h>

using namespace std;

typedef complex<double> base;
typedef long double ld;
typedef long long ll;

#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >

const int maxn=(int)(2e5+5);

vector< ll > fact(ll num)
{
vector< ll > ret;

for(ll i=2;i*1ll*i<=num;i++)
{
int ctr=0;

while(num%i==0)
{
num/=i;

ctr++;
}

if(ctr>0)
{
ret.pb(i);
}
}

if(num>1)
{
ret.pb(num);
}

return ret;
}

ll poww(ll a,ll b,ll mod)
{
ll x=1,y=a%mod;

while(b>0)
{
if(b%2==1)
{
x=(x*y)%mod;
}

y=(y*y)%mod;b/=2;
}

return (x%mod);
}

ll inv(ll a,ll mod)
{
return poww(a,mod-2,mod);
}

ll crt(vector< pll > v)
{
int n=v.size();

ll prod=1;

for(int i=0;i<n;i++)
{
prod*=v[i].second;
}

ll ret=0;

for(int i=0;i<n;i++)
{
ll now=prod/v[i].second;

ll zz=(v[i].first*inv(now,v[i].second))%prod;

zz=(zz*now)%prod;

ret=(ret+zz)%prod;
}

return ret;
}

int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);

int t;cin>>t;

ll val=31623;

while(t>0)
{
cout<<1<<" "<<val<<endl;

ll res;cin>>res;

res=(val*1ll*val)-res;

vector< ll > divs=fact(res);sort(divs.begin(),divs.end());

vector< pll > vec;set< ll > s;

if(divs.size()==1)
{
cout<<2<<" "<<divs[0]<<endl;
}

else
{

for(int i=0;i<divs.size();i++)
{
for(ll j=0;;j++)
{
ll zz=(j*1ll*j)%divs[i];

int prev=s.size();

s.insert(zz);

if(s.size()!=prev)
{
vec.pb({j,divs[i]});

break;
}
}
}

ll q=crt(vec);assert(q>0);

for(int i=0;i<vec.size();i++)
{
ll now=q%vec[i].second;

assert(now==vec[i].first);
}

cout<<1<<" "<<q<<endl;

ll get;cin>>get;ll ans=-1;

for(ll x:divs)
{
ll now=(q*1ll*q)%x;

if(now==get)
{
ans=x;

break;
}
}

cout<<2<<" "<<ans<<endl;
}

string qq;cin>>qq;

t--;
}

return 0;
}

8 Likes

Solution Without chinese remainder theorem: https://www.codechef.com/viewsolution/25295756

Explanation:

We can take x,y as any 2 different numbers between sqrt(n) and n, to reduce the time complexity we will take both which are nearer to sqrt(n) (n is max prime number = 10^9) such that they are not coprime.

We get 2 equation from the judge:
x^2 - a = 0 mod p
y^2 - b = 0 mod p
Now we find all the common prime factors from both the equation, and check if it satisfies the original equation, If it does (one of them will since answer always exists) then that’s the answer.

PS: I am not exactly sure why both the number x and y shouldn’t be coprime. @bohdan correct me if I am wrong anywhere.

8 Likes

I had the same approach but only got ac in 2 subtasks

2 Likes

Got AC after 30+ WA and TLE… : )

5 Likes

It is not clear to me why x^2 - a and y^2-b should only have a single common prime factor. If this is not the case, then your approach does not solve the exercise completely.

EDIT: So you just tried a lot of different x and y in separate submissions? I guess it is hard to make a testcase that is robust against this strategy.

It does not. That’s why we do this check.

No… Not really. You can’t just brute force any problem like that.
But I did tried it for a few numbers.
Those 30 WA are only because I panicked

1 Like

If you look at the tester’s solution he had a similar approach but instead of choosing 2 primes he chose A = 43222 and B = 40009

I’d love to know why, This is the only thing bugging me… @alipasha132 @kmaaszraa

3 Likes

Can u plz explain what happen if xand y have more than 1 prime common…plz explain I can’t understand this thing during contest too!!!
Thanks.

I am not sure, I tried a few possibilities (gdc=1, gcd!=1) and one passed.

Plz if u find any mathematical proof from anywhere, inform me…
Thanks…

My approach:

1. find prime factors using the first question . our prime number is among them.
2. select a number number whose square will give a unique remainder with each of the above prime and store the remainders.
3. match the input by chef with the stored remainders
my solution: https://www.codechef.com/viewsolution/25299376
2 Likes

Can you explain this in detail?

My approach is also same as yours.
My solution: https://www.codechef.com/viewsolution/25180544

2 Likes

Just brute force it. Since the number of prime factors can’t be more than 10 or 11.

1. select x= square root of largest prime
2. calculate x^2 for every prime
3. if they remainders are not unique increase x by 1 and goto 2
4. else ask for X ^ 2 % P
5. match input with remainders
also look at the solution
4 Likes

For finding a unique remainder:
I start a for loop from the largest prime factor I got upto 10000 and check which number gives me unique remainder for every prime factor.

2 Likes

I made an infinite loop.

1 Like

I didn’ used any CRT.
Just prime factorization and basic maths.

Here’s my approach:

1. We need to make sure we can find the prime number in two x queries.
So, as we can see x^2 mod P = ans1, here we can see that if P>x^2, we will get ans1 as x^2 only.
So, we can take 1st query x to cover up all prime number. i.e best way is to take 1st query of x
as sqrt(largest prime number).

2. If you see the primes, P which satisfies ans1 are all the prime factorization of num,
num= x^2-ans1

3.So next is we can store all the satisfied primes,P after query 1. and take the highest prime from it so we can find ‘x’ for our 2nd query.
which will be basically ceil(sqrt(highest prime))
We did that to cover up all the primes from our primes list which satisfied ans1

4.Now after getting ans2 from system we just iterate from our list and the one which satisfies is the prime number.

Here’s my solution: https://www.codechef.com/viewsolution/25220367

1 Like

Hahaah, you and I have the exact same idea Even I went upto 10000.

https://www.codechef.com/viewsolution/25263980