Hello codeforces. I have this problem from ECPC Qualifications. And i am really interested in solving it. I noteced that it can be solved using Mo's algorithm. But unfortinatly I need help to solve this problem

Can anyone please help me?

Hello codeforeces, I was trying to upsolve the ECPC Q day 2 and I am stuggle with this problem and need some help please.

I am thinking of using mo's algorithm but I can't solve this problem. Can any one help me please?

Hello codeforces, I am up-solving ECPC qualifications day 2 and i need some help in problem D.

After trying some tests i found that there is a pattern that repeat. and all the numbers between 0 and B-1 that is divisible by the GCD(A,B). And by the way I can easily calculate the the length of this cycle and also the sum of its number. the length = B/GCD(A,B) and the sum = (length*(length - 1)/2) * A Now we can solve the repeated cycles easily. But my problem is how to calculate the tail of it in O(1) .. i.e. lets say A = 1, B = 7, C = 10 ... we have only one repeated cycle which is from 0 to 6 and after that we will have remaining 3 number from the cycle. so we will need to calculate this what i call tail in O(1). as O(N) will get TLE due to the high test cases numbers.

Can anyone please help me with this problem?

Hello codeforces. I am trying to upsolve the problems of qualification day2 of ECPC and i need some help on this problem.

The solution that i implemented was a dp solution where dp[i] is the answer for i. so before run any testcase i calculate the dp from 1 to 1e6, and to do this i cal min(dp[i-1]+1, dp[i/j]+j) where j is every divisor of i.

I tried different codes to make this fast and the fasted code that came in my mind was by generate all the prime divisors of i and then calculate the all the divisors of each i from its prime divisors.

But even this code take around more than 3 seconds on my machine. Can anyone please help me with this problem? I want to know if my idea was right and if so will this solution pass in the contest? unfortunately they don't write the time for each test case

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18

using ull = unsigned long long;
using ll = long long;
using ui = unsigned int;

#define endl '\n'
#define newl cout<<endl;

void ICPC();

#define N 1000001
int dp[N+10];
int sp[N+10];
bool primes[N+10];

vector<int> getPD(int x) {
    vector<int> ret;
    while(x > 1) {
        ret.push_back(sp[x]);
        x /= sp[x];
    }
    return ret;
}

vector<int> st;
vector<int> tmp;

void genDiv(int ind, int val) {
    if(ind == tmp.size()) {
        st.push_back(val);
        return;
    }
    genDiv(ind+1, val);
    genDiv(ind+1, val*tmp[ind]);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    memset(primes, 1, sizeof(primes));
    primes[0] = primes[1] = 0;
    sp[1] = 1;
    for(int i = 2; i <= N; i+=2) sp[i] = 2;
    for(ll i = 3; i <= N; i+=2) {
        if(primes[i]) {
            sp[i] = i;
            for(ll j = i; j*i <= N; j+=2)
                if(primes[j*i]) primes[j*i] = 0, sp[j*i] = i;
        }
    }
    dp[0] = dp[1] = 0;
    for(int i = 2; i < N; i++) {
        dp[i] = dp[i-1]+1;
        tmp = getPD(i);
        st.clear();
        genDiv(0, 1);
        for(auto &x : st) {
            dp[i] = min(dp[i], dp[i/x]+x);
        }
    }

    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        ICPC();
        newl;
    }
}

void ICPC() {
    int n;
    cin >> n;
    int ans = 0, tmp;
    for(int i = 0; i < n; i++) {
        cin >> tmp;
        ans += dp[tmp];
    }
    cout << ans;
}

Hello codeforces. I noticed that most of Experienced Programmers prefer Iterative DP over Recursive one. I Know that some hard problem need space optimizations that can be done in iterative only. But I found that they always use the iterative DP. I see that the recursive DP is much easier. So what is the real purpose of that? Is the iterative solution is easier for them !?