PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Kishan Gadhiya
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni
DIFFICULTY:
2059
PREREQUISITES:
PROBLEM:
After solving some Graph Theory related problems KBG challenged Sameer to solve following problem.
You are given an integer N and Q queries. There is an undirected weighted edge between x and y for following conditions:
- 1 \leq x \leq N.
- y is divisor of x and weight of this edge will be x divide by y (x/y).
Each query is of the form:
- u v: Given two integers u and v (1 \leq u , v \leq N),
There is no multiple edges and self loops in graph.
For each query, find the minimum possible cost to reach v from u.
EXPLANATION:
We can always write v as u \times A / B, where A and B are integers > 1 (there are no self loops).
So, it is clear that there always exist a path of length at most 2 from u to v (u → (u \times A) → (v = u \times A / B)). The weight of this path is A + B.
For the minimum the path weight, there should not be any common factor of A and B (GCD(A, B) = 1) because in that case we can always divide A and B by their common factor to reduce the path weight. This leads to a contradiction!
We know that X \times Y \geq X + Y for X, Y \geq 2. This can be easily proved by taking the larger among X and Y to the left side of the inequality. Using this fact it is clear that if A or B can be broken into any 2 factors \geq 2 then we will reduce the path weight. In other words, if A = P \times Q, where P, Q \geq 2 then P + Q \leq A.
Hence, for the minimum path weight we will have to keep on breaking A and B into factors (\geq 2) so that no further breaking is possible. This clearly implies that we need prime factorization because primes cannot be broken further.
We can find out the prime factorization of u and v. Let u = 2^{u_1} \times 3^{u_2} \times 5^{u_3} ... and v = 2^{v_1} \times 3^{v_2} \times 5^{v_3} ... then the combined A / B factor can be written as 2^{v_1-u_1} \times 3^{v_2-u_2} \times 5^{v_3-u_3} ...
The path weight for this would be 2 \times abs(v_1-u_1) + 3 \times abs(v_2-u_2) + 5 \times abs(v_3 -u_3) + … because the weights add up for A and B as it is. This would be the minimum one for the reasons stated above.
This can be found out using prime factorization using sieve and a hash map.
TIME COMPLEXITY:
O(log(U)) + O(log(V)) for each test case and O(Nlog(log(N))) for precomputation.
SOLUTION:
Setter's solution
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = long double;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int , int>
#define int long long int
#define endl "\n"
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
// #define sz(v) (int) v.size()
#define PI 3.14159265358979323
#define inf LLONG_MAX
#define ones(x) __builtin_popcount(x)
#define mod 1000000007
#define MOD 998244353
ll mod_pow(ll a,ll b,ll m)
{
ll res = 1;
while(b)
{
if(b&1)
{
res=(res*a) % m;
}
a=(a*a) % m;
b>>=1;
}
return res;
}
ll mod_inverse(int a , int m)
{
return mod_pow(a , m - 2 , m);
}
const int N = 1e5 + 5;
int lpf[N];
void pre() {
for(int i = 2; i < N; ++i) {
if(lpf[i] == 0) {
for(int j = i; j < N; j += i) {
lpf[j] = i;
}
}
}
}
void solve()
{
int n , q;
cin >> n >> q;
for(int i = 0; i < q; ++i) {
int u , v;
cin >> u >> v;
int dummy_u = u;
int dummy_v = v;
map<int , int> frq;
while(dummy_u > 1) {
int y = lpf[dummy_u];
while(dummy_u % y == 0) {
dummy_u /= y;
frq[y] += 1;
}
}
while(dummy_v > 1) {
int y = lpf[dummy_v];
while(dummy_v % y == 0) {
dummy_v /= y;
frq[y] -= 1;
}
}
int res = 0;
for(auto r : frq) {
res += abs(r.S) * r.F;
}
cout << res << endl;
}
}
signed main() {
fast;
int t = 1;
pre();
cin >> t;
while(t--) {
solve();
}
return 0;
}
Editorialist's Solution
#define MAXN 100001
using namespace std;
int spf[MAXN];
void sieve(){
spf[1]=1;
for(int i=2;i<MAXN;i++)spf[i]=i;
for(int i=4;i<MAXN;i+=2)spf[i]=2;
for(int i=3;i*i<MAXN;i++){
if(spf[i]==i){
for(int j=i*i;j<MAXN;j+=i)
if(spf[j]==j)
spf[j]=i;
}
}
}
vector<int> getFactorization(int x){
vector<int>ret;
while(x!=1){
ret.push_back(spf[x]);
x=x/spf[x];
}
return ret;
}
int main() {
sieve();
int T;
cin >> T;
while(T--){
int N,Q;
cin >> N >> Q;
for(int i=0;i<Q;i++){
long long ans=0;
int U,V;
cin >> U >> V;
vector<int>res1=getFactorization(U);
map<int,int>ff;
for(auto x:res1)ff[x]++;
vector<int>res2=getFactorization(V);
for(auto x:res2)ff[x]--;
for(auto x:ff){
ans+=abs(x.second)*x.first;
}
cout << ans << endl;
}
}
return 0;
}
