PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Practice
Setter : Raj Khandor
Tester : Istvan Nagy
Editorialist : Anand Jaisingh
DIFFICULTY :
Medium
PREREQUISITES :
Bezout’s Identity, GCD properties, Sieve of Eratosthenes.
PROBLEM :
Given an integer array A of size N, you need to answer many queries over this array using an integer K. In a single query, you need to state the number of sub arrays of the given array whose GCD is a divisor of the integer K.
QUICK EXPLANATION :
We can use Bezout’s Identity to prove that for any given sequence b_1,b_2,...,b_m there exists another sequence c_1,c_2,....,c_m, such that \sum_{i=1}^{m} b_i \cdot c_i = K , if and only if GCD(b_1,b_2,...,b_m) is a divisor of the number K. Additionally, we can prove that if we fix the end point of a subarray (Let it be i) and vary it’s beginning points, then there can be at max O(\log(A[i])) distinct values among GCD's of all these subarrays. We can find all these GCD values in \approx \log^2(A[i]) time, leading to an overall runtime of O(N \cdot \log^2(A[i])) time. Finally, we use Sieve of Eratosthenes, so that queries can be easily answered in O(1).
EXPLANATION :
The first part of the problem is identifying for a given integer X, and a set of integers \{b_1,b_2,.....b_m \} , how to know if there exists another set of integers \{ c_1,c_2,....,c_m \}
such that \sum_{i=1}^{m} b_i \cdot c_i = X
The answer my friends is quite well known. Let’s consider the general case, when m=2. We are given 2 integers b_1,b_2 and an integer X. Can we find some c_1,c_2 satisfying our requirements ?
Bezout’s identity tells us that there exist such c_1,c_2 if and only if GCD(b_1,b_2) divides X. If it does, then in fact here exist infinitely pairs (c_1,c_2).
It’s not too difficult to see that we can in fact extend m, and the fact that there exists such (c_1,c_2,....,c_m) exists only if GCD(b_1,b_2,....,b_m) divides X holds true. You can prove this on your own, or read it here
So, our original task now converts to finding for some K, the number of subarrays whose GCD is a divisor of K.
Now, let’s proceed to part 2 :
Claim : For a fixed index i, there exists at most O(log(A[i])) distinct values of subarray GCD’s among all subarrays ending at index i.
Proof :
It’s easy to see that the GCD function is a decreasing function. That is, if i < j <k , then GCD(a[i],a[i+1],,,a[j]) \ge GCD(a[i],a[i+1],....a[k]). And when we transition from j to k, if GCD(a[i],a[i+1],....a[j]) \ne GCD(a[i],a[i+1],....a[k]), then GCD(a[i],a[i+1],....,a[j]) is divided by some positive integer z > 1 to get GCD(a[i],a[i+1],.....,a[k]).
Just consider, if all the numbers (a[i],a[i+1],...a[k]) share a common factor then the numbers (a[i],a[i+1],...a[j]) also share this factor (The GCD) but they can possibly share even more factors even after division by the GCD.
And since the maximum number of times a number a[i] can be divided by a number z > 1 is \log(a[i]), hence proved.
So, if we know how many subarrays ending at index i have GCD equal to X for each possible X (Remember there are only at max O(log(A[i])) ones), then we can find in O(log(a[i+1]) ) time easily, for each Y, the number of subarrays ending at index (i+1) having GCD equal to Y.
The values of Y can only be among the values of GCD(X,a[i]). It easy to see, that if many subarrays all have GCD equal to X and ending at index i, then when we append index i+1 to the end of all the subarrays, then their GCD will be GCD(X,a[i+1]).
In this process, we can know for each possible integer X, the number of subarrays having GCD equal to X over the whole array. Let’s call this val[x].
Now, we just do a simple Sieve, and for some fixed x, add to all multiples of x, \hspace{0.2cm} val[x] . I.e. something of the kind :
\forall \hspace{0.2cm} i, \hspace{0.2cm} \forall \hspace{0.2cm} j \ge 2, val[ i \cdot j] += val[i]
Later, when we need to answer queries, we can answer each of them easily in O(1).
That’s it, thank you !
Your comments are welcome !
COMPLEXITY ANALYSIS :
Time Complexity : O(N \cdot \log^2 A[i] + Q + N \cdot \log N )
Space Complexity : O(N \cdot \log N )
SOLUTION LINKS :
Setter
#include <bits/stdc++.h>
using namespace std;
#define maxK 1000001
//#define DEBUG
typedef long long int ll;
ll sieve[maxK];
int main()
{
#ifdef DEBUG
ifstream cin("4.in");
ofstream cout("4.out");
#endif
ll n,g;
cin>>n;
ll a[n];
for(int i=0;i<n;i++)
cin>>a[i];
map<ll,ll> m;
map<ll,ll> gcds;
for(int i=0;i<n;i++)
{
// m contains gcds of all the subarrays ending at index i-1
// m1 contains gcds of all the subarrays ending at i
map<ll,ll> m1;
for(auto itr = m.begin(); itr!= m.end(); itr++)
{
g = __gcd(a[i], itr->first);
m1[g] += itr->second;
gcds[g] += itr->second;
}
m1[a[i]]++;
gcds[a[i]]++;
m = m1;
}
for(int i=0;i<maxK;i++)
sieve[i] = 0;
ll i,val;
ll maxi = INT_MIN;
for(auto itr = gcds.begin(); itr!=gcds.end(); itr++)
{
i = itr->first;
val = itr->second;
for(int j=i;j<maxK;j+=i)
sieve[j] += val;
}
for(int i=0;i<maxK;i++)
maxi = max(sieve[i]*1ll, maxi);
int q,x;
cin>>q;
while(q--)
{
cin>>x;
cout<<sieve[x]<<"\n";
}
return 0;
}
Tester
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}
int main(int argc, char** argv)
{
#ifdef HOME
if (IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int N, Q, K, query;
scanf("%d", &N);
const int MAXK = 1e6 + 2;
const int MAXJ = 20;
vector<int> A(N);
vector<int64_t> B(MAXK);
vector<vector<int> > AA(MAXJ, vector<int>(N));
for (uint32_t i = 0; i < N; ++i)
{
scanf("%d", &A[i]);
}
AA[0] = A;
for (uint32_t j = 1; (1 << j) <= N; ++j)
{
auto& actA = AA[j];
for (uint32_t i = 0; i < N; ++i) if(i + (1<<j) <= N)
{
actA[i] = gcd(AA[j - 1][i], AA[j - 1][i + (1 << (j-1))]);
}
}
for (uint32_t i = 0; i < N; ++i)
{
int act = A[i];
int actP = i, lastP = i;
++actP;
while (actP < N && act > 1)
{
int newP = actP;
for (uint32_t j = 0; actP + (1 << j) <= N; ++j)
{
if (gcd(act, AA[j][actP]) != act)
{
break;
}
else
{
newP = actP + (1 << j);
}
}
if (newP == actP)
{
if (act < MAXK) B[act]+=(actP-lastP);
act = gcd(act, A[actP]);
lastP = actP;
++actP;
}
else
{
actP = newP;
}
}
if (act < MAXK) B[act] += (N - lastP);
}
scanf("%d", &Q);
for (uint32_t q = 0; q < Q; ++q)
{
scanf("%d", &query);
int64_t ans = 0;
for (int i = 1; i * i <= query; ++i) if(query % i == 0)
{
ans += B[i];
if(i*i != query)
ans += B[query/i];
}
printf("%d\n", ans);
}
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);
const ll mod=(ll)(1e9+7);
int a[maxn];
ll res[1000006];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
map<int,ll> m1;
for(int i=0;i<n;i++)
{
map<int,ll> m2;
for(auto x:m1)
{
int now=__gcd(x.first,a[i]);
m2[now]+=m1[x.first];
}
m2[a[i]]++;
for(auto x:m2)
{
if(x.first<=1000000)
{
res[x.first]+=x.second;
}
}
m1=m2;
}
/*
for(int i=1;i<=10;i++)
{
cout<<res[i]<<" ";
}
*/
cout<<endl;
for(int i=1000000;i>=1;i--)
{
for(int j=i+i;j<=1000000;j+=i)
{
res[j]+=res[i];
}
}
int q;cin>>q;
while(q>0)
{
int x;cin>>x;
cout<<res[x]<<endl;
q--;
}
return 0;
}
,
