SJ1 - Editorial

easy
editorial
gcd
number-theory
april19

#45

https://www.codechef.com/viewsolution/24041293

Please help
Can anyone point out problem in my code. I am getting TLE for all cases except 1 case. I have commented my code thoroughly.


#46

Hi! Thanks for the question. Since you’re going to take coefficients modulo m_{l_i} in the end, it doesn’t matter. You may just take m-k instead of -k to obtain needed remainder.


#47

I did not get the following things:

  1. Why is it assured the equation will have a solution if g/g’ and m/g’ are coprime?
  2. How can we substitute g with g’?

From the other answer, I can see that gcd is the interval which separates successive multiples of g’ but how can I prove that generally?
Any suggested reading that I should go through?


#48

Pass graph “adj” by reference in your function. Everytime the function is called, graph is copied! Hence, TLE.


#49

Solution for linear diophantine equation with co-prime numbers may be obtained by extended euclidean algorithm. We may substitute g with g' because equation g'=kg \pmod{m} has a solution so set of numbers which occur in arithmetic progression of g is the same as set of numbers which occur in arithmetic progression of g'.


#50

Tried almost everything, but getting runtime error for first 9 testcases

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> tree[10001];
ll val[10001];
ll m[10001];
ll res[10001];
vector<ll> leaf;
ll _gcd(ll a, ll b){
    if(a<b)
    return _gcd(b,a);
    if(b==0)
    return a;
    return _gcd(b,a%b);
}
void cal(int x, int p, ll gcd){
    gcd = _gcd(gcd,val[x]);
    
    for(auto u: tree[x]){
            if(u==p)
                continue;
            cal(u,x,gcd);
        }
        
    if(tree[x].size()==1 && x!=1){
        leaf.push_back(x);
        res[x] = m[x]-_gcd(m[x],gcd);
    }
}
int main() 
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
    	
        int n;
        cin>>n;
        if(!leaf.empty())
        leaf.clear();
        for(int i=1; i<=n; i++)
            tree[i].clear();
        int a,b;
        for(int i=0; i<n-1; i++){
            cin>>a>>b;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }

        for(int i=1; i<=n; i++)
            cin>>val[i];
        for(int i=1; i<=n; i++)
            cin>>m[i];

        cal(1,0,val[1]);
        sort(leaf.begin(),leaf.end());
        int sz = leaf.size();
        for(int i=0; i<sz; i++)
            cout<<res[leaf[i]]<<" ";
        cout<<"\n";
    }
    return 0;
}

#51

Your explanation made everything much easier. Thanks a lot for your patience and explanation.


#52

you should be putting the if(G[i].size()==1) in DFS, outside the if(T[i] == false).


#53

Could you explain why we chose undirected graph ?


#54

input format says ‘there is an edge between x and y’ and not ‘there is an edge frm x to y’
hence input for was in that format thats why you shld choose undirected graph
assume the graph to be undirected if not given in ques for future probs