 # GN_THEORY - Editorial

Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

2059

# PREREQUISITES:

Prime Factorization

# 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;
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;
}



https://www.codechef.com/viewsolution/67945388
WA test cases feature not working on my solution… The approach is same as that of the editorial…if anyone could debug/make claim on correctness it would be of great help.

1 Like

You can check my code if it helps.

Code

1 Like

Line number 28 to line number 41 is wrong, that’s not how linear sieve is done. Linear Sieve - Algorithms for Competitive Programming (cp-algorithms.com)

A simpler code

That is correct…The bug was in the query, where I set prime factor to -1 once a prime factor matches…It affects the next query where same number is asked.

I am not getting the fact where the code is failing. Can u please explain? #include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace chrono;
// using namespace __gnu_pbds;

#define int long long
#define ld long double
#define endl "\n"
#define pi  3.141592653589
#define INF 1e18
#define vi  vector<int>
#define vvi vector<vector<int>>
#define mi map<int,int>
#define mpi map<pair<int,int>,int>
#define vpi vector<pair<int,int>>
#define pr  pair<int,int>
#define mp  make_pair
#define triplet pair<int,pair<int,int>>
#define ff first
#define ss second
#define pb push_back
#define MAX INT_MAX
#define MIN INT_MIN
#define fr(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b) for(int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define pD(x,y) cout<<fixed<<setprecision(y)<<x
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define mod 998244353
#define LMAX 9223372036854775807
const int MOD=1e9+7;
const int GN=1e7+10;
#define upperToLower(x) char(x | ' ')
#define lowerToUpper(x) char(x & '_')

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<bool> sieve(GN,1);
int dsieve[GN];
vi fact(GN,1);

/*---------------------------------------------------------------------------------------------------------------------------*/
bool isPrime(int n){for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return true;}
void primeSieve(){sieve = sieve = false;for (int i = 2; i*i<= GN; i++) {if (sieve[i]) {for (int j = i*i; j <= GN; j += i)sieve[j] = false;}}}
void divSieve(){for(int i=1;i*i<=GN;i++){for(int j=i;j<=GN;j=j+i){++dsieve[j];}}}
vector<vector<int>> matProd(vector<vector<int>> A,vector<vector<int>> B,int size){int sum=0;vector<vector<int>> C(size);
for(int i=0;i<size;i++){for(int j=0;j<size;j++){for(int k=0;k<size;k++){sum+=A[i][k]*B[k][j];}C[i].pb(sum);sum=0;}}return C;}
vector<vector<int>> matExp(vector<vector<int>> A,int n,int size){
if(n==0){for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(i==j) A[i][j]=1; else A[i][j]=0;}}return A;}
if(n==1)return A;
vector<vector<int>> temp=matExp(A,n/2,size);if(n%2==0)return matProd(temp,temp,size);else return matProd(A,matProd(temp,temp,size),size);}
vector<int> prefixSum(vector<int> &A){vector<int> res(A.size());res=A;for(int i=1;i<A.size();i++){res[i]=A[i]+res[i-1];} return res;}
void printMatrix(vector<vector<int>> &A,int n,int m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<A[i][j]<<" ";}cout<<endl;}}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int binexp(int x,int n){int a=x;int prod=1;while(n){if(n%2==1)prod=prod*a;a=a*a;n=n/2;    }return prod;}
map<int,int> primeFactorisation(int n){map<int,int> mpp;for(int i=2;i*i<=n;i++){if(n%i==0){int cnt=0;while(n%i==0){++cnt;n=n/i;}mpp[i]=cnt;}}if(n>1)mpp[n]=1;return mpp;}
vector<int> merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> temp;int ptr1=0;int ptr2=0;int c=0;while(true){if(ptr1==m || ptr2==n)break;if(nums1[ptr1]<nums2[ptr2]){temp.push_back(nums1[ptr1]);ptr1++;}else{temp.push_back(nums2[ptr2]);ptr2++;}c++;}for(int i=ptr1;i<m;i++){temp.push_back(nums1[i]);c++;}for(int i=ptr2;i<n;i++){temp.push_back(nums2[i]);c++;}return temp;}
int modexp(int a, int b, int m) {a %= m;int res = 1LL;while (b > 0) {if (b & 1)res = (res%m *1LL* a%m) % m;a = (a%m *1LL* a%m) % m;b >>= 1;}return res%m;}
void factSieve(){for(int i=1;i<GN;i++)fact[i]=(fact[i-1]%MOD*1LL*i%MOD)%MOD;}
int modinv(int a){return modexp(a,MOD-2,MOD);}
int nCr(int n,int r){int nmr=fact[n]%MOD;int dmr=(fact[r]%MOD*1LL*fact[n-r]%MOD)%MOD;return (nmr%MOD *1LL* modinv(dmr)%MOD)%MOD;}
/*--------------------------------------------------------------------------------------------------------------------------*/

void solve()
{
int T;
cin>>T;
while(T--)
{
int n,q;
cin>>n>>q;

vector<vector<pair<int,int>>> graph(n+10);
for(int i=1;i<=n;i++){
for(int j=i*2;j<=n;j+=i){
graph[i].pb({j,j/i});
graph[j].pb({i,j/i});
}
}
// NLogN
// Dijkstra
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,1});
vi dist(n+10,INT_MAX);
dist=0;
dist=0;
while(!pq.empty())
{
int nodeNum=pq.top().second;
int currDist=pq.top().first;
pq.pop();
for(auto &it : graph[nodeNum])
{
int wt=it.second;
{
}
}
}
while(q--)
{
int u,v;
cin>>u>>v;
if(u==v)
{
cout<<0<<endl;
continue;
}
int pu=min(u,v);
int pv=max(u,v);

int g=__gcd(pu,pv);
if(g>1)
{
if(pv%pu==0)
{
cout<<pv/pu<<endl;
}
else
cout<<pu/g + pv/g<<endl;
}
// g=1
else{
cout<<dist[u]+dist[v]<<endl;
}
}

}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
auto start1 = high_resolution_clock::now();
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
cerr << "Time : " << duration . count() / 1000 << endl;

return 0;
}



Loved this problem!!

1 Like

can anyone tell me what will be the answer for u = 6 and v = 36.

In here suppose pu =2, and pv = 20

but we can actually go in 7 moves. 2->10 ->20 (5+2)

5 as we can go from 6 to 12 then from 12 to 36 , := 12/6 + 36/12 = 2 + 3 = 5

but according to editorial gcd will be 6 so answer should be 6/6 + 36/6 = 6.