PROBLEM LINK:
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\times…p_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\times…p_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;
}