PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Setter : Bohdan Pastuschak
Tester : Alipasha Montaseri / Kasra Mazaheri
Editorialist : Anand Jaisingh
DIFFICULTY :
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.
- 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 .
- 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];
int ask(int x)
{
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;
}
Even I went upto 10000.