# UQR - Editorial

**URL:** <https://discuss.codechef.com/t/uqr-editorial/118104>\
**Category:** editorial\
**Tags:** editorial, math, start137\
**Created:** [June 5, 2024, 2:40am UTC](https://discuss.codechef.com/t/uqr-editorial/118104 "2024-06-05T02:40:49Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [June 5, 2024, 2:40am UTC](https://discuss.codechef.com/t/uqr-editorial/118104/1 "2024-06-05T02:40:50Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/UQR)  
[Contest: Division 1](https://www.codechef.com/START137A/problems/UQR)  
[Contest: Division 2](https://www.codechef.com/START137B/problems/UQR)  
[Contest: Division 3](https://www.codechef.com/START137C/problems/UQR)  
[Contest: Division 4](https://www.codechef.com/START137D/problems/UQR)

_ **Author:** _ [helloLad](https://www.codechef.com/users/helloLad)  
_ **Tester:** _ [sky\_nik](https://www.codechef.com/users/sky_nik)  
_ **Editorialist:** _ [iceknight1093](https://www.codechef.com/users/iceknight1093)

# DIFFICULTY:

TBD

# PREREQUISITES:

Math

# PROBLEM:

You are given N, A, B. It is guaranteed that |A-B| \leq 1.  
Find the number of integers X such that 1 \leq X \leq N, and there exist non-negative integers p and q such that Ap + Bq = X.

# EXPLANATION:

Without loss of generality, let A \leq B.  
Since |A-B| \leq 1, we must have either A = B or A+1 = B.

If A = B, the only numbers that can be formed are multiples of A, that is, A, 2A, 3A, \ldots  
So, the answer is simply the number of positive multiples of A that don’t exceed A, which is \displaystyle \left\lfloor \frac{N}{A} \right\rfloor.

Now, we look at the A+1 = B case; in simpler words we want to know which numbers \leq N can be formed by adding copies of A and (A+1).  
If you work out a few small cases, you might observe that:

- It’s impossible to reach any X \lt A.
- A and A+1 can be reached.
- It’s impossible to reach any A+1 \lt X \lt 2A.
- 2A, 2A+1, 2A+2 can be reached.
- It’s impossible to reach any 2A+2 \lt X \lt 3A.
- Everything from 3A to 3A+3 can be reached.  
\vdots

Extrapolating this, it seems useful to look at integers of the form pA + q.  
Note that we only need to consider q \lt A, since if q \geq A we could just increase p by 1 and decrease q by A.  
Henceforth, we only consider q \lt A.

From what was observed above, a reasonable guess is that we can reach pA + q if and only if p \geq q.  
It’s not hard to prove the correctness of this.  
[details = Proof]  
If p\geq q, it’s easy to reach pA + q - take q copies of (A+1) and (p-q) copies of A.

if p \lt q, then combined with the fact that q \lt A, observe that we need _at least_ q copies of A+1 — after all, copies of A don’t change the remainder modulo A while copies of (A+1) increase by 1, and we want the remainder modulo A to be q.  
But then taking q copies of (A+1) already puts us at a value of qA + q, which is strictly larger than pA + q.  
So, it’s impossible to form pA + q when p \lt q \lt A.

[/details]

So, we want to count the number of integers \leq N that can be written as pA + q, for p \geq q and q \lt A.  
(Note that for a fixed integer X, this choice of p and q is unique since we enforced 0 \leq q \lt A - they’re just the quotient and remainder when X is divided by A.)

That can be done quickly with a bit of math:

- There are two valid values \lt 2A.
- There are three valid values \lt 3A but \geq 2A.
- There are four valid values \lt 4A but \geq 3A.  
\vdots

This continues till we reach A^2 = A\cdot A, where there are A valid values \lt A^2 and \geq A\cdot (A-1).  
Then, for any m\geq A, there will always be only A (and not m) valid values between (m-1)A and mA-1, because there are only A values in that range at all.

So, let k = \left\lfloor \frac{N}{A} \right\rfloor.  
Then,

- If k \leq A, the count is 2 + 3 + \ldots + k.
- If k \gt A, the count is 2 + 3 + \ldots + A + (k-A)\cdot A.

Both of these can be computed in constant time.  
Note that these aren’t quite the final answers: we only considered blocks of length A, while the final block might be of length \lt A (in particular, it will have length (N\bmod A)).  
This final block can be taken care of specially: p is fixed for it, so just count the number of valid q, which shouldn’t be hard if you’ve come this far.

# TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

# CODE:

[details = Author’s code (C++)]

```cpp
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

int main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        long long n,a,b;
        cin>>n>>a>>b;
        assert(abs(a-b)<=1);
        if(a==b){
            cout<<n/a<<'\n';
            continue;
        }
        if(a>b){
            swap(a,b);
        }
        long long k=n/a;
        if(k==0){
            cout<<0<<'\n';
            continue;
        }
        long long res=n;
        res-=(a-max(1LL,a-k))*(max(1LL,a-k)+a-1)/2;
        if(k<a-1){
            res-=max(0LL,n-a*k-k);
        }
        cout<<res<<'\n';
    }
    return 0;
}

```

[/details]  
[details = Tester’s code (C++)]

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

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int t; cin >> t; while (t--) {
    int64_t n, a, b;
    cin >> n >> a >> b;

    if (a == b) {
      cout << n / a << '\n';
      continue;
    }

    if (a > b) {
      swap(a, b);
    }
    assert(b == a + 1);

    if (n < a) {
      cout << 0 << '\n';
      continue;
    }

    // Chicken McNugget Theorem
    if (n >= (a - 1) * a) {
      cout << n - ((a - 1) * a) / 2 << '\n';
      continue;
    }

    const auto quo = n / a;
    const auto rem = n % a;
    cout << (quo * (quo + 1)) / 2 + min(quo, rem) << '\n';
  }
}

```

[/details]  
[details = Editorialist’s code (Python)]

```python
for _ in range(int(input())):
    n, a, b = map(int, input().split())
    if a == b:
        print(n//a)
        continue
    a = min(a, b)
    k = n//a
    if k == 0:
        print(0)
        continue
    
    ans = 0
    if k >= a:
        ans = a*(a+1)//2 + (k-a)*a - 1
    else:
        ans = k*(k+1)//2 - 1
    ans += min(n%a, k)+1 # Last block
    print(ans)

```

[/details]

---

<div class="post-metadata">

**Author:** ![dask0\_0](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dask0_0/32/295681_2.png) [@dask0\_0](https://discuss.codechef.com/u/dask0_0)\
**Post date:** [June 6, 2024, 5:09am UTC](https://discuss.codechef.com/t/uqr-editorial/118104/3 "2024-06-06T05:09:11Z")

</div>

Can the tester explain what the Chicken McNugget Theorem is ?

---

<div class="post-metadata">

**Author:** ![nskybytskyi](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nskybytskyi/32/292494_2.png) [@nskybytskyi](https://discuss.codechef.com/u/nskybytskyi)\
**Post date:** [June 6, 2024, 7:15am UTC](https://discuss.codechef.com/t/uqr-editorial/118104/4 "2024-06-06T07:15:44Z")

</div>

I recommend reading about [Chicken McNugget Theorem](https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem) on AOPS. It tells you two things: the largest number X^\* that cannot be expressed as A \cdot p + B \cdot q, and how many numbers 1 \le X \le X^\* cannot be expressed in this form. Therefore, one can use it to answer cases with N \ge X^\* quickly.