DIVISIBLEBY - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: satyam_343
Testers: IceKnight1093, tejas10p
Editorialist: IceKnight1093

DIFFICULTY:

1569

PREREQUISITES:

Basic knowledge of gcd

PROBLEM:

Let f(B, x) be the smallest integer y such that x divides every y\cdot B_i.
Given an array A, compute f(A, A_i) for each 1 \leq i \leq N.

EXPLANATION:

First, let’s see how to compute f(A, A_1): then we can extend this to everything else.

For a given i, what are the values of y such that y\cdot A_i is divisible by A_1?
Well, intuitively y should contain all those factors of A_1 that are not in A_1.

So, let’s take A_1 and remove all the common factors of A_1 and A_i from it, giving us \displaystyle \frac{A_1}{\gcd(A_1, A_i)}.
Note that any valid y should be a multiple of this value.

Now, we want y to be the smallest possible multiply of every such value.
Similar reasoning should tell you that we choose \displaystyle y = \frac{A_1}{\gcd(A_1, A_2, \ldots, A_N)}.

Why?

Notice that to get \displaystyle \frac{A_1}{\gcd(A_1, A_i)}, we removed all the common factors of A_1 and A_i since those were redundant.

What if there were two values, say A_i and A_j?
Well, the redundant factors in this case are the ones common to all three of A_1, A_i, A_j, which is exactly \gcd(A_1, A_i, A_j).

Extending this to all N positions gives us the above result.

Now that we have this, note that the denominator, \gcd(A_1, A_2, \ldots, A_N) is a constant.

So, let’s first compute g = \gcd(A_1, \ldots, A_N) by iterating across the array.

Then, \displaystyle f(A, A_i) = \frac{A_i}{g} which can be computed in \mathcal{O}(1).

TIME COMPLEXITY:

\mathcal{O}(N + \log\max A) per testcase.

CODE:

Setter's code (C++)
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;  
#define ll long long  
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;    
#define pb push_back                 
#define mp make_pair          
#define nline "\n"                           
#define f first                                          
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
#define vl vector<ll>           
#define vvl vector<vector<ll>>    
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);    
#endif       
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;}     
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;     
const ll MAX=2002;  
ll pw(ll x,ll ex){
    ll now=1;
    while(ex--){
        now=(now*x)%MOD;
    }      
    return now;
}  
void solve(){   
    ll n; cin>>n;    
    vector<ll> a(n+5,0);  
    ll g=0;  
    for(ll i=1;i<=n;i++){
        cin>>a[i]; 
        g=__gcd(g,a[i]);
    }       
    for(ll i=1;i<=n;i++){
        a[i]/=g;
        cout<<a[i]<<" \n"[i==n]; 
    }
    return;                                  
}                                                
int main()                                                                                             
{        
    ios_base::sync_with_stdio(false);                           
    cin.tie(NULL);    
    #ifndef ONLINE_JUDGE                   
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);    
    freopen("error.txt", "w", stderr);                        
    #endif                          
    ll test_cases=1;               
    cin>>test_cases;
    while(test_cases--){
        solve();
    } 
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}  
Tester's code (C++)
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;  
#define ll long long  
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;    
#define pb push_back                 
#define mp make_pair          
#define nline "\n"                           
#define f first                                          
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
#define vl vector<ll>           
#define vvl vector<vector<ll>>    
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);    
#endif       
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;}     
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;     
const ll MAX=2002;  
ll pw(ll x,ll ex){
    ll now=1;
    while(ex--){
        now=(now*x)%MOD;
    }      
    return now;
}  
void solve(){   
    ll n; cin>>n;    
    vector<ll> a(n+5,0);  
    ll g=0;  
    for(ll i=1;i<=n;i++){
        cin>>a[i]; 
        g=__gcd(g,a[i]);
    }       
    for(ll i=1;i<=n;i++){
        a[i]/=g;
        cout<<a[i]<<" \n"[i==n]; 
    }
    return;                                  
}                                                
int main()                                                                                             
{        
    ios_base::sync_with_stdio(false);                           
    cin.tie(NULL);    
    #ifndef ONLINE_JUDGE                   
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);    
    freopen("error.txt", "w", stderr);                        
    #endif                          
    ll test_cases=1;               
    cin>>test_cases;
    while(test_cases--){
        solve();
    } 
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}  
Editorialist's code (Python)
from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = gcd(*a)
	print(*[x//g for x in a])