In this HackerEarth Special Matrix problem solution, you have an N x M matrix, where 1 to N are rows and 1 to M are columns.
Element at the intersection of ith row and jth column is equal to F(i + j), where F(x) is equal to the number of prime divisors of x. Determine the sum of all the elements of the matrix.
HackerEarth Special matrix problem solution.
#include "bits/stdc++.h"
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
for ( \
auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
blockTime.second; \
debug("%s: %d ms\n", d, (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
)
#ifdef LOCAL
#include "pprint.hpp"
#endif
#define endl '\n';
#define pb push_back
#define mod 1000000007
#define ll long long int
#define prn(x) cerr<<x<<endl;
#define all(x) x.begin(),x.end()
using namespace std;
#define test_case 1
const int Mx = 2e6+5;
vector<int> v, p;
void solution(){
int n,m;
cin>>n>>m;
assert(n>=1 && n<=1000000);
assert(m>=1 && m<=1000000);
if(n<m)
swap(n,m);
ll ans=0;
for(int i=1;i<=n;++i){
int tot=min(i,m);
ans += (ll)v[i+1]*(ll)tot;
}
int tot=m-1;
for(int i=2;i<=m;++i){
ans += (ll)v[n+i]*(ll)tot;
tot--;
}
cout<<ans<<endl;
}
int main(int argc, char *argv[])
{
#ifdef LOCAL
freopen("in.txt" , "r" , stdin);
#else
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
#endif
p.assign(Mx+5,1);
v.assign(Mx+5,0);
p[0]=p[1]=0;
for(int i=2;i<Mx;++i)
if(p[i])
for(int j=i;j<Mx;j+=i){
v[j]++;
p[j]=0;
}
int t=1;
if(test_case)
cin>>t;
assert(t>=1 && t<=10);
time__("Solution Time"){
while(t--){
solution();
}
}
return 0;
}
0 Comments