FORFS-Editorial

PROBLEM LINK:

Practice
iitv.str()

Author: vikiwarrior
Co - Author & Tester: valiant_vidit
Tester: hellb0y_suru
Editorialist: vikiwarrior

DIFFICULTY:

EASY

PROBLEM:

Given a number C=A \times B which has n factors (not necessarily prime factors) a_1,a_2,a_3,a_4,a_5...a_n . Find ANS,where ANS=F(a_1)+F(a_2)+F(a_3)+F(a_4)+.....+F(a_n) and F(x)=p_1 \times q_1+p_2 \times q_2+p_3 \times q_3 +.....p_m \times q_m
where prime factorisation of x is is x=p_1q_1\times p_2q_2\times p_3q_3\timesp_mq_m

EXPLANATION:

In this question, we can use a bit of basic maths or some mathematical induction.

Firstly, instead of multiplying A and B straightaway to find C and then prime factorizing C we can prime factorize A and B separately and then add the powers of common primes in both A and B. For example, if

A=2^3 \times 3^1 \times 7 and B = 2^2 \times 3^2 \times 11 then prime factorisation of C=2 (3+2) \times 3 (1+2) \times 7 \times 11=2^5 \times 3^3 \times 7 \times 11

Prime factorization of A and B can be generated using the sieve method which takes O(n) time to build. So, the total time complexity is O(n+ c \times T \times log(n) ),where c is a constant.

Now using mathematical induction or some observation it can be proved that

If prime factorization of C is,C=p_1q_1 \times p_2q_2\times p_3q_3\timesp_mq_m

ANS=(p_1 \times \displaystyle\sum_{x=1}^{q_1}x )\times (q_2 +1) \times (q3 +1)...\times (q_m +1) )+ ((q_1 +1) \times (p_2 \times \displaystyle\sum_{x=1}^{q_2}x ) \times (q3 +1)... . \times (q_m +1)) + . ......... . ((q_1 +1) \times (q_2 +1) \times (q_3 +1)... .\times(p_m \times \displaystyle\sum_{x=1}^{q_m}x ))

This can be simplified to :
ANS= \displaystyle\sum_{i=1}^{m}((p_i \times \displaystyle\sum_{x=1}^{q_i}x ) \times (pr/(q_i+1)))

here pr= ((q_1 +1) \times (q_2 +1) \times (q_3 +1)... .\times(q_m +1 ))

Tip: To derive this result start with small numbers and then try to generalize it.

SOLUTIONS:

Setter's Solution
  #include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
int spf[10000010];
 
void pre(){
    for(int i=1;i<=10000000;i++) spf[i]=i;
    for(int i=2;i<=10000000;i++){
        if(spf[i]==i){
            for(int j=2*i;j<=10000000;j+=i){
                if(spf[j]==j) spf[j]=i;
            }
        }
    }
}
 
void sol(){
    int a,b; cin >> a >> b;
    map<int,int> m;
    int x = a;
    while(x>1){
        m[spf[x]]++;
        x/=spf[x];
    }
    x = b;
    while(x>1){
        m[spf[x]]++;
        x/=spf[x];
    }
    long long int tot = 1;
    for(auto &i: m) tot *= (i.second+1);
    long long int ans = 0;
    for(auto &i: m){
        long long int cnt = (i.first*i.second*tot)/2;
        ans += cnt;
    }
    cout << ans <<"\n";
 
    return;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    pre();
    int t; cin >> t;
    while(t--) sol();
}
Tester's Solution
/*author : vidit shukla
           (valiant_vidit)*/
#pragma  GCC optimize("O3")
#include <bits/stdc++.h>
#define ll               long long int
#define bhaago           ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define loop(a,b,i)      for(ll i=a;i<b;i++)
#define loop1(a,b,i)     for(ll i=a;i>b;i--)
#define printclock       cerr<<"Time : "<<1000*(double)clock()/(double)CLOCKS_PER_SEC<<"ms\n";
#define endl              '\n'
#define yy               cout<<"YES"<<endl
#define nn               cout<<"NO"<<endl
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
const double pi = std::acos(-1);
using namespace std;
const ll mod = 1000000000+7;
 
ll power(ll x,ll y,ll md)  
{ll res=1;x=x%md;if(x==0)return 0;while(y>0){if(y&1)res=(res*x)%md;y=y>>1;x=(x*x)%md;}return res;} 
 
ll m_mul(ll a, ll b){a=a%mod;b=b%mod;return (a*b+mod)%mod;}
ll m_add(ll a,ll b){a=a%mod; b=b%mod;return (a+b+mod)%mod;}
 
ll spf[(ll)1e7+2]={0};
void siv()
{
spf[1]=1;
loop(1,1e7+2,i)
spf[i]=i;
 
loop(2,1e7+2,i)
spf[i]=2,i++;
for(ll i=3;i*i<(ll)1e7+2;i++)
{  
   if( spf[i]==i)
    for(ll j=i*i;j<(ll)1e7+2;j=j+i)
    if(spf[j]==j)spf[j]=i;
}
 
}
ll geta1(ll a,unordered_map<ll,ll> &mp)
{
    ll ans=0;
  //  map<ll,ll>mp;
    while(a!=1)
    {
        mp[spf[a]]++;
        a=a/spf[a];
    }
ll pr=1;
    // for(auto it:mp)
    // {
    //    pr=pr*(it.second+1);
    // }
    // for(auto it:mp)
    // {
    //     cout<<it.first<<"-->"<<it.second<<endl;
    // }
    // for(auto it:mp)
    // {
    //     ans=ans+(it.first)(((it.second)(it.second+1))/2)*(pr/it.second);
    // }
return ans;
 
}
int main() {
      bhaago;
     // freopen("@input.txt","r",stdin);
    //  freopen("@output.txt","w",stdout);
    ll tc=1;
    siv();
    printclock
    cin>>tc;
    while(tc--)
    {
        ll a,b;
        cin>>a>>b;
        unordered_map<ll,ll>mp;
        geta1(a,mp);
        geta1(b,mp);
 
        ll pr=1,ans=0;
        for(auto it:mp)
    {
       pr=pr*(it.second+1);
    }
    // for(auto it:mp)
    // {
    //     cout<<it.first<<"-->"<<it.second<<endl;
    // }
    // cout<<pr<<endl;
    for(auto it:mp)
    {
        ans=ans+(it.first)*(((it.second)*(it.second+1))/2)*(pr/(it.second+1));
    //    cout<<"ans"<<ans<<endl;
    }
    cout<<ans<<endl;
 
        
       
    //  cout<<n<<endl;
        
    }
    printclock
	// your code goes here
	return 0;
}
4 Likes