I am using the idea, x < b and when x = r * lcm + [0, b — 1] ==> (x % a) % b = (x % a) % a So, I am using this idea to solve the problem, but my code is failing I don't know why it is missing some cases please help me with this Problem link, Submission Link

#include <iostream>

using namespace std;

#define ws ' '
#define ll long long

ll gcd(ll a, ll b) {
   if (b > a) swap(a, b);
   while (b != 0) {
       ll temp = b;
       b = a % b;
       a = temp;
   }

   return a;
}

ll f(ll _lcm, ll b, ll r) {
    ll ans = min(r, b - 1);
    ll d = (r - b + 1) / _lcm;
    if (d != 0) {
        ans += d * b;
        if ((d + 1) * _lcm <= r) ans += (r - (d + 1) * _lcm + 1);
    }

    return ans;
}




void solve() {
    ll a, b, q;
    cin >> a >> b >> q;
    ll _lcm = (a * b) / (gcd(b, a));
    while (q--) {
        ll l, r;
        cin >> l >> r;
        ll ans = r - l + 1;
        ans -= f(_lcm, b, r);
        if (l > 0) ans += f(_lcm, b, l - 1);
        cout << ans << ws;
    }
    
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(__null);
    
    int t = 1;
    cin >> t;

    for (int _ = 0; _ < t; _++) solve();

    return 0;
}

Link to the problem You are given a tetrahedron. Let's mark its vertices with letters A, B, C and D correspondingly.

your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (1e9 + 7).

Idea is simple,

Use the above mentioned recursive relations to find out the answer

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> fD(n + 1), fA(n + 1);
    fD[0] = 1;
    fA[0] = 0;

    for (int i = 1; i <= n; ++i) {
        fD[i] = (3 * fA[i - 1]) % MOD;
        fA[i] = (2 * fA[i - 1] + fD[i - 1]) % MOD;
    }

    cout << fD[n] << endl;
    return 0;
}

Optimized code can be found here (DP solution Click here for code)

Further optimized code (Click here for code)

Solutions are discussed in this video