CIRCHAOS - Editorial

PROBLEM LINK:

Contest

Setter : Pranav Rajagopalan
Tester : Rahul Dugar
Editorialist : Rajarshi Basu

DIFFICULTY:

Easy

PREREQUISITE:

Modulos, GCD, and factorisation

PROBLEM:

You are an evil sorcerer at a round table with N sorcerers (including yourself). You can cast M spells which have distinct powers p_1, p_2, \ldots, p_M.

You may perform the following operation any number of times (possibly zero):

  • Assign a living sorcerer to each positive integer cyclically to your left starting from yourself ― the closest living sorcerer to your left is assigned to 1, the next living sorcerer to the left is assigned to 2 and so on. Note that each living sorcerer (including yourself) is assigned to an infinite number of integers.
  • Choose a spell j (possibly a spell you have chosen before) and kill the living sorcerer assigned to p_j. You may not cast a spell to kill yourself.

What is the maximum number of sorcerers you can kill using zero or more operations?

Constraints

  • 1 \le T \le 1,000
  • 1 \le N \le 10^9
  • 1 \le M \le 3 \cdot 10^5
  • 1 \le p_i \le 10^9 for each valid i
  • p_1, p_2, \ldots, p_N are pairwise distinct
  • the sum of M over all test cases does not exceed 3 \cdot 10^5

BRIEF EXPLANATION:

One-liner

Let X = gcd(p[1], p[2], p[3] … p[n]). Let Y = \max\limits_{f | X, f \leq n} f. Answer is n - Y.

EXPLANATION:

Observation 1

Let us use the smallest p[i], WLOG assuming it to be p[0]. Let us also assume that n > p[0]. Then, we can always keep taking p[0]^{th} ALIVE candidate. However, we can only do so till n = p[0], since we cannot kill ourselves. How can we use this?

Observation 2

When p[0] = n, we can try using the other p[i] values right? They shouldn’t always refer to ourself, so we can use them to kill more stuff. Again, once we kill atleast one more person, n < p[0] which means we can again keep using p[0] (due to modular arithmetic nature of the question), till n | p[0] right?

Observation 3

The above thing doesn’t work only when we have n | p[0] , n | p[1], n | p[2] … n | p[m]. Can we do anything then? No! That means, once n reaches this stage, we cannot kill anymore people! That means the limiting value of n is gcd(p[0], p[1], … , p[m]).

Observation 4 - Final Solution

What if n < gcd(p[…]) ? Well, then any factor f | gcd(p[…]) also acts as a limiting value. Hence, n ’s reduction is going to be limited by the greatest factor f of the gcd value. Now, make sense of the brief solution!

SOLUTION:

Tester’s Code
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
int suss=0;
void solve() {
//	int n=readIntSp(1,1'000'000'000),m=readIntLn(1,300000);
	int n,m;
	cin>>n>>m;
	suss+=m;
//	assert(suss<=300000);
	int spoll=0;
	vi ffff;
	fr(i,1,m) {
		int te;
		cin>>te;
//		if(i!=m)
//			te=readIntSp(1,1'000'000'000);
//		else
//			te=readIntLn(1,1'000'000'000);
		spoll=__gcd(spoll,te);
	}
	int ori=0;
	for(int i=1; i*i<=spoll; i++) {
		if(spoll%i==0) {
			int pp=i,ppp=spoll/i;
			if(n>=pp)
				ori=max(ori,pp);
			if(n>=ppp)
				ori=max(ori,ppp);
		}
	}
	cout<<n-ori<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
//	int t=readIntLn(1,1000);
	int t;
	cin>>t;
	fr(i,1,t)
		solve();
//	assert(getchar()==EOF);
#ifdef rd
//	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

VIDEO EDITORIAL:

6 Likes

What a wonderful problem !!

4 Likes

We only needed to find the largest divisor of the gcd(=g) which is less than or equal to n. This can be done in \mathcal{O} (\sqrt{g}) time. Few solutions that iterated through all numbers less than or equal n until getting to a required one are accepted. n and g can be as large as 10^9 and along with 1000 test cases, this solution should have clearly got a TLE.

1 Like

Bro please make test cases strong .

4 Likes

This problem is mind-blowing.

2 Likes

The code in the editorial is not readable.

7 Likes

okay, smart pants, notice that if g>n then that means n<= 3e6 ,which is why those soultions are accepted.
edit : also g will aways be in the range 3e6, because all elements are <= 3e6

Good Problems should have Good editorial too.
The approach mentioned is not at all clear and intuitive.

4 Likes

what does
n∣p[0]
mean in observation 2?

What if n=10^9-1,m=1,p_1=10^9? This will fail even for a single test case. You say that elements are \le 3\cdot 10^6 which is not true, check the constraints again. Even if they were, 1000 test cases ensure that it gives TLE.

Can someone help me with some testcase where my code would fail? Thanks.
https://www.codechef.com/viewsolution/40755602

n=m=4, p = [8, 9, 12, 15]. The answer should be 3.

yeah my code outputs 3 on this testcase.

No, it gives 1.