Given an array A, for each element of the array find the number of elements in the array that are divisible by the element and also occur before it.
INPUT FORMAT
The first line contains a single integer N
The second line contains N integers representing the array A
CONSTRAINTS
1 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^6
OUTPUT FORMAT
print N lines containing one integer
SAMPLE INPUT
7
8 1 28 4 2 6 7
SAMPLE OUTPUT
0
1
0
2
3
0
1
I hope the question is clear. simple approach is to run a loop for element to find the no. of elements divided by it. But it’s complexity is O(N^2) which will get TLE for sure. Can someone help me out in providing a better approach 
PS : this problem is not from any ongoing contest 
, it was asked in my institution.
I hope I can trust you.
Let’s reframe the problem: Given an array A, for each element of the array, find the number of elements in the array that are divisors of the element and also occur after it.
Note that we can find out the divisors of an element in O(\sqrt n) time. Thus, we can store the indices of each element in a data structure like a map or something, and for each divisor of the element, if the divisor occurs after that element in the array, we can increment the counter for the answer of that index.
4 Likes
You have given me an idea. Thanks. Now i understand 
1 Like
Here_is_the_same_problem
@galencolin @anon49701446 help me in this i tried two approach -
-
Precompute divisiors of all number from 1 to 10^6 and do same thing as @anon49701446 said (GOT TLE)
-
Instead of precompute find out divisiors of each element at runtime and do same thing as @anon49701446 said (got 25 marks)
#include <bits/stdc++.h>
using namespace std;
vector<int>all_div[100001];
void alldivisors(){
for(int i=1;i<=100000;++i){
for(int j=i;j<=100000;j+=i)
all_div[j].push_back(i);
}
}
int main() {
alldivisors();
int n;
cin>>n;
int a[n];
int b[n]={0};
map<int,vector<int>>mp;
for(int i=0;i<n;i++){
cin>>a[i];
mp[a[i]].push_back(i);
}
for(int i=0;i<n;i++){
for(auto xt : all_div[a[i]]){
if(mp.find(xt)!=mp.end()){
for(auto xr : mp[xt]){
if(xr>i){
b[xr]++;
}
}
}
}
}
for(int i=0;i<n;i++)cout<<b[i]<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
int b[n]={0};
unordered_map<int,vector<int>>mp;
for(int i=0;i<n;i++){
cin>>a[i];
mp[a[i]].push_back(i);
}
for(int i=0;i<n;i++){
int val = a[i];
for(int j=1;j*j<=val;j++){
if(val%j==0){
if(mp.find(j)!=mp.end()){
for(auto xr : mp[j]){
if(xr>i){
b[xr]++;
}
}
}
if(j!=val/j and mp.find(val/j)!=mp.end()){
for(auto xr : mp[val/j]){
if(xr>i){
b[xr]++;
}
}
}
}
}
}
for(int i=0;i<n;i++)cout<<b[i]<<endl;
return 0;
}
- The first problem is that you’re only doing divisors up to 10^5
- Try a testcase with 5 \cdot 10^4 of 2 and 5 \cdot 10^4 of 1.
The solution by @anon49701446 will also fail for a case like that, unless they meant something else, because that makes it O(n^2) to update each index.
Let’s instead do the opposite of the opposite, and maintain the answer for all numbers at once. That is, we’ll know for each number as we go along, “if this array element were x, what would its answer be?”
Consider some element a_i. Any candidate a_j where i will contribute to its answer has to be a divisor of a_i. So let’s keep an array c of size 10^6 + 1, initially filled with 0. Then, sweep to the right, and when encountering an a_i, first take its answer which is c[a_i], then increment the value of c at all divisors of a_i, including itself. Any divisor of a_i to the right of it will now consider a_i as part of its answer.
Complexity is O(10^6\log{10^6} + n \cdot (10^6)^{\frac{1}{3}}) (first part is to find the divisors, second part is because each number x can have around x^\frac{1}{3} divisors).
Means I have to write this for finding divisiors of all elements in NlogN complexity right?
vector<int>all_div[1000001];
void alldivisors(){
for(int i=1;i<=1000000;++i){
for(int j=i;j<=1000000;j+=i)
all_div[j].push_back(i);
}
}
I called alldivisors function and do nothing for main code and it shows TLE …WTH
That code looks right
Uh… no clue why it TLE’s like that, that shouldn’t happen
I wrote this 
#include <bits/stdc++.h>
using namespace std;
vector<int>all_div[1000001];
void alldivisors(){
for(int i=1;i<=1000000;++i){
for(int j=i;j<=1000000;j+=i)
all_div[j].push_back(i);
}
}
int main() {
alldivisors();
int n;
cin>>n;
int a[n];
int b[n]={0};
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++)cout<<b[i]<<endl;
return 0;
}
and got TLE …
Try using fast i/o and '\n' instead of endl
Yeah, indeed it will TLE. My bad. Thanks for the correction @galencolin. 
2 Likes
U r from same university from which i shared the link…please tell the solution as contest is organized by u people
No this is for @rishiikesavan he is from Madras Institute of Technology (same clg which host contest for 2nd year).
1 Like
Oh, sorry for the misunderstanding. I thought you replied to my comment. My bad, again.
1 Like
this code will take more than 1 sec…so most of the ide’s give TLE…
Try submitting in codechef ide itself and know the execution time
If u have better approach or more better AC solution then please tell
It’s concept is similar to October 2k19 long challenge question MSV, solving that first might get you AC.
Thank you very much AC in one go… I also solved in Long but i forgot
void increaseallfac(lli n , lli tot[]){
for(lli i=1;i*i<=n;i++){
if(n%i==0){
if(n/i == i)
tot[i]++;
else{
tot[i]++;
tot[n/i]++;
}
}
}
}
int main(){
fastIO
lli t=1;
//cin>>t;
while(t--){
lli x,n;
cin>>n;
lli a[n];
scanarr(a,n);
lli maxxx = *max_element(a,a+n);
lli tot[maxxx+1]={0};
lli maxi =0;
loop(i,n){
cout<<tot[a[i]]<<endl;
increaseallfac(a[i],tot);
}
}
return 0;
}
@galencolin Firstly i can’t understand your approach but after @ronythakur said this is similar like Oct - long i open my solution and understands what u said and what is the basic thought behind this … Thanks
As it turns out, your code is exactly what my approach was
1 Like