Modular Array - Editorial

Problem Link:

problem

Authors and Editorialists: Shivam Sahni, Amey Kulkarni

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Chinese Remainder Theorem, Extended Euclidean Theorem

PROBLEM:

Replace the -1's in an array according to the following equation-
r_i \equiv r_j \bmod i, where (i, j) pairs, such that j is a multiple of i.
If there are multiple ways to fill in the array, considering you have already filled all −1 entries for the previous indices with valid values, fill it with the smallest value possible.

QUICK EXPLANATION:

For each -1 entry, form two equations using co-prime numbers of the Chinese Remainder theorem form whose product is the index of the -1 entry and solve them using the Extended Euclidean algorithm.

EXPLANATION:

Check validity of the original array

Any given number depends on the values of its multiples. In other words, any number dictates the possible values that its factors may take. Hence an array will be valid iff
r_i \equiv r_j \bmod i, where (i, j) pairs, such that j is a multiple of i, and r_j is not originally -1.
For checking this, we can iterate over the array from right to left and check this condition. Remember, you also have to fill r_i with r_j \bmod i, if r_j is not -1.

Form the Chinese Remainder Theorem equations

If the array is valid, it means there exists at least one way to assign values to -1's, from Chinese Remainder theorem.

Case 1 - At least two prime factors

The equations formed for r_i will depend on the values at all r_f's, where f represents any factor of i. However, we claim that only two equations:
r_{f_1} \equiv r_i \bmod f_1
r_{f_2} \equiv r_i \bmod f_2
such that gcd(f_1, f_2) = 1 are required, and f_1 \times f_2 = i.
(Note: The above is not valid if there exist less that two prime factors of i).

Case 2 - Composite number, exactly one prime factor

If i has only one prime factor p but i \neq p, r_i = r_{i/p}

Case 3 - The number is prime

If i is a prime number, r_i = 0,

Solving for Case 1

We can use Extended Euclidean Algorithm to solve Case 1.

Time Complexity

O(Nlog(N)), since for each index we need to check values at its multiples.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#include <iostream>
#define mod 1000000007
#define ll long long
#define vi vector<int>
#define vii vector<vector<int>>
#define fo(i,n) for(int i=0;i<n;i++)
#define pb(x) push_back(x)
#define ci(x) cin>>x
#define ci2(x,y) cin>>x>>y
#define ci3(x,y,z) cin>>x>>y>>z
#define co(x) cout<<x<<endl
#define co2(x,y) cout<<x<<' '<<y<<endl
#define co3(x,y,z) cout<<x<<' '<<y<<' '<<z<<endl

using namespace std;

vi sieve;
vi num_pfacs;
int N = 2 * 100001;

int gcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int g = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return g;
}

vi ex_gcd(int n1, int n2){
    bool rev = false;
    //co2(n1, n2);
    if(n1 < n2){
        rev = true;
        int temp = n1;
        n1 = n2;
        n2 = temp;
    }
    int x = 0, y = 0;
    int g = gcd(n1, n2, x, y);
    vi K(2);
    if(rev){
        K[0] = y;
        K[1] = x;
    }
    else{
        K[0] = x;
        K[1] = y;
    }
    //co2(x, y);
    return K;
}

int extended_euler(int i, vi &a){
    ll num = i;
    ll num1 = 1;
    int pfac1 = sieve[i];
    while(sieve[i] == pfac1){
        num1 *= pfac1;
        i /= pfac1;
    }
    ll num2 = i;
    ll a1 = a[num1];
    ll a2 = a[num2];
    vi K = ex_gcd(num1, num2);
    ll k1 = (a2 - a1) * K[0], k2 = -(a2 - a1) * K[1];
    //co2(k1, k2);
    assert(num1 * k1 + a1 == num2 * k2 + a2);
    ll ans = (num1 * k1 + a1) % (num);
    if(ans < 0)
        ans += num;
    return ans;
}

void test(){
    int n;
    cin>>n;
    vi a(n + 1);
    fo(i, n){
        cin>>a[i + 1];
    }
    
    // Preprocessing
    for(int i = n; i >= 1; i--){
        for(int j = i; j <= n; j += i){
            if(a[j] != -1){
                if(a[i] == -1){
                    a[i] = a[j] % i;
                }
                else if(a[i] != a[j] % i){
                    cout<<-1<<endl;
                    return;
                }
            }
        }
    }

    for(int i = 1; i <= n; i++){
        if(a[i] == -1){
            if(i == 1){
                a[i] = 0;
            }
            else if(sieve[i] == i){
                a[i] = 0;
            }
            else if(num_pfacs[i] == 1){
                int larg_fac = i / sieve[i];
                a[i] = a[larg_fac];
            }
            else{
                a[i] = extended_euler(i, a);
            }
        }
    }
    fo(i, n){
        cout<<a[i + 1]<<' ';
    }
    cout<<endl;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    sieve.resize(N, 0);
    num_pfacs.resize(N, 0);
    for(int i = 2; i < N; i++){
        if(sieve[i] == 0){
            for(int j = i; j < N; j += i){
                num_pfacs[j] += 1;
                if(sieve[j] == 0)
                    sieve[j] = i;
            }
        }
    }

    int t;
    cin>>t;
    while(t--){
        test();
    }
}
Editorialist's Solution
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define vi vector <int>
#define vvi vector <vi>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define sz(v) ((int)(v).size())
#define all(v) v.begin(), v.end()
#define MOD 1000000007
using namespace std;
const ll MAX_N = 1e5 + 10;
ll mxprime[MAX_N];
vector <ll> prime;

void sieve(){
    mxprime[1] = 1;
    for (ll i=2; i<MAX_N; i++){
        if (mxprime[i]==0){
            prime.pb(i);
            for (ll j=i; j<MAX_N; j+=i){
                mxprime[j] = i;
            }
        }
    }
}

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}



int main(){

#ifndef ONLINE_JUDGE 
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout); 
#endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t; cin>>t;
    sieve();
    while (t--){
        int n; cin>>n;
        vi a(n+1);
        for (int i=1; i<n+1; i++) cin>>a[i];
        bool val = true;     
        for (int i=n; i>0; i--){
            for (int j=2*i; j<n+1; j+=i){
                if (a[j]!=-1){
                    ll t1 = a[j] % i;
                    if (a[i]==-1) a[i] = t1;
                    else{
                        if (a[i]!=t1) val = false;
                    }
                }
            }
        }

        if (val){
            for (ll i=1; i<n+1; i++){
                if (a[i]==-1){
                    if (mxprime[i]==i) {
                        a[i] = 0;
                        continue;
                    }
                    vi a_prm;
                    int tmp = i;
                    while (tmp!=1){
                        int t1 = mxprime[tmp];
                        int t2 = 1;
                        while (tmp%t1==0){
                            tmp/=t1;
                            t2 *= t1;
                        }
                        a_prm.pb(t2);
                    }

                    if (sz(a_prm)==1){
                        a[i] = a[i/mxprime[i]];
                    }
                    else{
                        ll t1 = a_prm[0];
                        ll t2 = i/a_prm[0];
                        ll x, y;
                        exgcd(t1, t2, x, y);
                        x *= -1 * (a[t1] - a[t2]);
                        y *= a[t1] - a[t2];
                        a[i] = ((a[t1] + t1 * x ) % i + i) % i;
                        ll tmp = ((a[t2] + t2 * y) % i + i) % i;
                        assert (a[i] == tmp);
                    }
                }
            }
            for (int i=1; i<n+1; i++){
                cout<<a[i]<<" ";
            } cout<<endl;
        }
        else{
            cout<<-1<<endl;
        }
    }

    return 0;
}
3 Likes