PROBLEM LINK :
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