KETEKI2C editorial

PROBLEM LINK :

Practice
Contest

Setter: Chirag Thakur

Tester: Harsh Raj

Editorialist: Harsh Raj

DIFFICULTY:

Easy

PREREQUISITES:

Factorisation, Modular Multiplicative Inverse

EXPLAINATION:

Total number of factors of a number is product of frequencies
 of its prime factors incremented by 1.


For each element in array A, store the frequency of all its 
prime factors. Count number of factors of product of all 
elements using the above explaination. Since the number of 
factors can be huge, use modulous at each step. Now for each 
index i, remove the contribution in product from A[i]. Use
multiplicative inverse for this. Finally print the sum mdulo 
1e9+7

SOLUTIONS:

Settler's Solution

	#include <bits/stdc++.h>
	using namespace std;
	 
	string to_string(string s) {
	  return '"' + s + '"';
	}
	 
	string to_string(const char* s) {
	  return to_string((string) s);
	}
	 
	string to_string(bool b) {
	  return (b ? "true" : "false");
	}
	 
	template <typename A, typename B>
	string to_string(pair<A, B> p) {
	  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
	}
	 
	template <typename A>
	string to_string(A v) {
	  bool first = true;
	  string res = "{";
	  for (const auto &x : v) {
	    if (!first) {
	      res += ", ";
	    }
	    first = false;
	    res += to_string(x);
	  }
	  res += "}";
	  return res;
	}
	 
	void debug_out() { cerr << endl; }
	 
	template <typename Head, typename... Tail>
	void debug_out(Head H, Tail... T) {
	  cerr << " " << to_string(H);
	  debug_out(T...);
	}
	 
	#ifdef LOCAL
	#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
	#else
	#define debug(...) 42
	#endif
	 
	template <uint32_t mod>
	class Modular {
	private:
	  uint32_t n;
	 
	public:
	  Modular(int64_t _n = 0) : n((_n >= 0 ? _n : mod - (-_n) % mod) % mod) {}
	 
	  uint32_t get() const {
	    return n;
	  }
	 
	  bool operator ==(const Modular& o) const {
	    return n == o.n;
	  }
	 
	  bool operator !=(const Modular& o) const {
	    return n != o.n;
	  }
	 
	  Modular& operator +=(const Modular& o) {
	    n += o.n;
	    n = (n < mod ? n : n - mod);
	    return *this; 
	  }
	 
	  Modular& operator -=(const Modular& o) {
	    n += mod - o.n;
	    n = (n < mod ? n : n - mod);
	    return *this;
	  }
	 
	  Modular& operator *=(const Modular& o) {
	    n = uint64_t(n) * o.n % mod;
	    return *this;
	  }
	 
	  Modular& operator /=(const Modular& o) {
	    return (*this) *= o.inv();
	  }
	 
	  Modular operator +(const Modular& o) const {
	    return Modular(*this) += o;
	  }
	 
	  Modular operator -(const Modular& o) const {
	    return Modular(*this) -= o;
	  }
	 
	  Modular operator *(const Modular& o) const {
	    return Modular(*this) *= o;
	  }
	 
	  Modular operator /(const Modular& o) const {
	    return Modular(*this) /= o;
	  }
	 
	  Modular pow(uint64_t b) const {
	    Modular ans(1), m = Modular(*this);
	    while (b) {
	      if (b & 1) {
	        ans *= m;
	      }
	      m *= m;
	      b >>= 1;
	    }
	    return ans;
	  }
	 
	  Modular inv() const {
	    int32_t a = n, b = mod, u = 0, v = 1;
	    while (a) {
	      int32_t t = b / a;
	      b -= t * a;
	      swap(a, b);
	      u -= t * v;
	      swap(u, v);
	    }
	    assert(b == 1);
	    return Modular(u);
	  }
	};
	 
	using Mint = Modular<int(1e9 + 7)>;
	 
	void test_case() {
	  int n;
	  cin >> n;
	  map<int, int> cnt;
	  vector<int> A(n + 1);
	  for (int i = 1; i <= n; ++i) {
	    cin >> A[i];
	    int num = A[i];
	    for (int f = 2; f * f <= num; ++f) {
	      if (num % f == 0) {
	        int foo = 0;
	        while (num % f == 0) {
	          num /= f;
	          ++foo;
	        }
	        cnt[f] += foo;
	      }
	    }
	    if (num != 1) {
	      ++cnt[num];
	    }
	  }
	  Mint tot(1);
	  for (auto p : cnt) {
	    tot *= p.second + 1;
	  }
	  vector<Mint> b(n + 1, tot);
	  for (int i = 1; i <= n; ++i) {
	    int num = A[i];
	    for (int f = 2; f * f <= num; ++f) {
	      if (num % f == 0) {
	        int foo = 0;
	        while (num % f == 0) {
	          num /= f;
	          ++foo;
	        }
	        b[i] /= cnt[f] + 1;
	        b[i] *= cnt[f] - foo + 1;
	      }
	    }
	    if (num != 1) {
	      b[i] /= cnt[num] + 1;
	      b[i] *= cnt[num];
	    }
	  }
	  cout << accumulate(b.begin() + 1, b.end(), Mint(0)).get() << "\n";
	}
	 
	int main() {
	  ios_base::sync_with_stdio(0);
	  cin.tie(0);
	  cout.tie(0);
	  test_case();
	  return 0;
	}

Tester's Solution

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long int
	#define eb emplace_back
	const int mod=1e9+7;
	#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#define endl "\n"
	 
	// there can be max 20 primes whose product is less than 1e18
	// so all map related calculations is expected to take constant time
	map<int,int> find_primes(int target);
	 
	int gcdExtended(int a, int b, int *x, int *y){ 
	    // Base Case 
	    if (a == 0){ 
	        *x = 0, *y = 1; 
	        return b; 
	    } 
	  
	    int x1, y1; // To store results of recursive call 
	    int gcd = gcdExtended(b%a, a, &x1, &y1); 
	  
	    // Update x and y using results of recursive 
	    // call 
	    *x = y1 - (b/a) * x1; 
	    *y = x1; 
	  
	    return gcd; 
	}
	 
	int modInverse(int a, int m){ 
	    int x, y; 
	    int g = gcdExtended(a, m, &x, &y); 
	    if (g != 1) 
	        return 1;// 
	    else{ 
	        // m is added to handle negative x 
	        int res = (x%m + m) % m; 
	        return res;
	    } 
	} 
	 
	int main(){
		IOS;	//fast input-output
		ll i,j,k,n,m,ans=0,variable=1;
		cin>>n;
	 
		vector<int> a(n),b(n),c(n);
		vector<map<int,int> > res(n);	//stores all prime factors of a[i] with their count
		map<int,int> look_up;	//stores count of all primes 
	 
		for(i=0;i<n;i++){
			cin>>a[i];
			res[i]=find_primes(a[i]);
			for(auto it:res[i])
				look_up[it.first]+=it.second;
		}
		// for(i=0;i<n;i++)	//not needed
		// 	b[i]=product/a[i];
	 
		for(auto it:look_up){//product of all (powers+1) of prime factors of a[i]
			variable*=(it.second+1)%mod;
			variable%=mod;
		}
		
		for(i=0;i<n;i++){
			ll var=variable;	
			for(auto it:res[i]){	
				//remove contribution due to primes of a[i]
				var*=(modInverse(look_up[it.first]+1,mod));
				var%=mod;
				var*=(look_up[it.first]-(it.second)+1);
				var%=mod;
			}
			ans+=(var)%mod;	
			ans%=mod;
			// cout<<"ans now is "<<ans<<" with "<<var<<endl;
		}
		cout<<ans<<"\n";
		return 0;
	}
	 
	map<int,int> find_primes(int target){	//find count all prime factors in O(sqrt(n))
		int var=target,limit=ceil(sqrt(target)+1);
		map<int,int> ans;
		for(int i=2;i<limit;i++){
			while(var%i==0 && var>0){
				ans[i]++;
				var/=i;
			}
		}
		if(var > 1)//if the target is a prime
			ans[var]++;
		return ans;
	}

Do Share your approach as well. Suggestions are Welcomed :innocent:

Plz explain me how to remove contribution of A[i] element…

we have stored the frequency of each prime factor for all array values in a map arr_map
and frequency of prime factor of each array element in map freq[i]

we store the value of number of factors of array by traversing arr_map let it be arr_product

and now we are traversing input array and want to remove contribution of A[i]

what we are doing :-

  1. Remove the contribution of prime ‘a’ from the arr_product
  2. then add the contribution of prime ‘a’ of all the array elements except the current element which can be evaluated by total frequency of prime a in the array - frequency of prime ‘a’ current array element i.e. arr_map[a] - freq[i][a]

let there are 4 prime divisors of the current A[i] i.e. {a,b,c,d}

so to remove the contribution of prime ‘a’ in arr_product
take modInverse of arr_map[a] + 1 and then we add the contribution of all the array elements except the current element arr_map[a] - freq[i][a] +1

we are adding 1 because there are P+1 factors if frequency of prime ‘a’ is P

by this we can do this process for every prime factor of A[i] and can compute our answer

link to solution :- https://www.codechef.com/viewsolution/25423378

1 Like

Can anyone explain what is wrong in my approach?

https://www.codechef.com/viewsolution/25364514