In this case any $$$a[i] \gt =b[i]$$$ for all $$$(1 \lt =i \lt =n)$$$, you can easily make a[i]%b[i]==0 by decreasing the value of a[i] or increase the value of b[i] with cost 0, and for this conditon b[i]>a[i] only the cost is 1.

#include <bits/stdc++.h>
 
using namespace std;
 
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define testcase int t; cin>>t; for(int i=0;i<t;i++)
 
#define ll long long int
ll lcm(ll a, ll b) {
    return (a / __gcd(a, b)) * b;
}
 
 
void solved(){
	/*start*/
    ll n;
    cin>>n;
    vector <ll> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector <ll> b(n);
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    ll cnt=0;
    for(int i=0;i<n;i++){
        if(a[i]<b[i]){
            cnt+=(b[i]-a[i]);
        }
    }
    cout<<cnt<<"\n";
	/*end*/
}
 
int main(){
	faster
	testcase 
	solved();
}

In this, to minimise the number of string h, we will count the character that is extra from s, then we can make exactly (extra_char_left_count+k-1)/k;

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
	ll t;
	cin>>t;
	while(t--){
	    ll n,m,k;
	    cin>>n>>m>>k;
	    string s,p;
	    cin>>s>>p;
	    int l=0,i=0;
	    while(l<m&&i<n){
	        if(s[i]==p[l]){
	            l++;
	        }
	        i++;
	    }
	    if(l==m){
	        cout<<(n-m+k-1)/k<<"\n";
	    }
	    else{
	        cout<<"-1\n";
	    }
	}
	
}

Inside each group, if the most frequent value $$$mx$$$ is less than or equal to half the group size $$$sz$$$, you can pair almost everyone. If $$$mx \gt sz/2$$$, you are forced to have $$$sz - 2(sz - mx)$$$ leftovers of that specific value. Globally, the same principle applies: the maximum inter-group pairs you can form is limited by the "gap" between the total leftovers and the most dominant leftover value.

The total answer is the sum of local pairs plus these budgeted global pairs. This ensures you only "buy" matches that are physically possible to form given the leftover value constraints.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
 
void solve() {
    int n , k , c;
   cin >> n >> k >> c;
 
    vector<int> a(n) , b(n);
    for (int i=0;i<n;i++) {
        cin >> a[i];
    }
 
    for (int i=0;i<n;i++) {
        cin >> b[i];
    }
 
    map<int, map<int, int>> m;
    for (int i=0;i<n;i++) {
        m[b[i]][a[i]]++;
    }
 
    int ans = 0;
    int tot = 0;
    int g_mx = 0;
    map<int, int> rem;
 
    for (auto it : m) {
        map<int, int> &group = it.second;
        
        int sz = 0;
        int mx = 0;
        int dom = -1;
 
        for (auto c_it : group) {
            int cnt = c_it.second;
            int cl = c_it.first;
            sz += cnt;
            if (cnt > mx) {
                mx = cnt;
                dom = cl;
            }
        }
 
        if (mx > sz / 2) {
            int p = sz - mx;
            ans += p;
            int r = sz - (2 * p);
            rem[dom] += r;
            tot += r;
        } 
        else {
            ans += sz / 2;
            if (sz % 2 != 0) {
                tot += 1;
            }
        }
    }
 
    for (auto r_it : rem) {
        if (r_it.second > g_mx) {
            g_mx = r_it.second;
        }
    }
 
    int can_p = tot / 2;
    if (tot - g_mx < can_p) {
        can_p = tot - g_mx;
    }
 
    int bud_p = (c / k) * 2;
 
    int paid = can_p;
    if (bud_p < paid) {
        paid = bud_p;
    }
 
    cout << ans + paid << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

1. The Supermask Principle: For any chosen bitwise AND sum $$$S$$$, the largest possible subsequence we can form consists of all integers $$$x \in [l, r]$$$ such that $$$x \text{ AND } S = S$$$. Adding any such $$$x$$$ to our set does not decrease the bitwise AND sum, meaning the condition $$$S \ge k$$$ remains satisfied while the length $$$m$$$ increases. Thus, the problem is equivalent to finding an $$$S \ge k$$$ that maximizes the count of its supermasks in the range.

2. The Candidate Space Proof: We do not need to check every $$$S \in [k, r]$$$. We only need to check $$$k$$$ itself and the set of "bit-minimal" integers greater than $$$k$$$. These are formed by: Picking a bit $$$i$$$ that is unset ($$$0$$$) in $$$k$$$. Setting bit $$$i$$$ to $$$1$$$ and clearing all bits $$$j \lt i$$$ to $$$0$$$. Any other value $$$S' \gt k$$$ that is not one of these candidates will be a supermask of either $$$k$$$ or one of these candidates. Since a supermask of $$$S'$$$ is also a supermask of any value $$$S \subset S'$$$, the count of supermasks for our candidates will always be greater than or equal to the count for any arbitrary $$$S'$$$.

3. Combinatorial Counting: For a fixed mask $$$S$$$, the number of integers $$$x \le N$$$ that satisfy $$$x \text{ AND } S = S$$$ can be calculated in $$$O(\log N)$$$ using a digit-based approach. If $$$S$$$ has $$$b$$$ bits set, and we are considering a range of $$$W$$$ bits, there are $$$W - b$$$ "free" bits. The number of ways to fill these bits such that the result is $$$\le N$$$ follows a standard combinatorial path: at any bit position $$$i$$$ where $$$N$$$ has a $$$1$$$ and $$$S$$$ has a $$$0$$$, we can set that bit to $$$0$$$ and freely choose all subsequent "free" bits below it ($$$2^f$$$ combinations).

Conclusion: By testing only $$$O(\log r)$$$ candidate masks and using the inclusion-exclusion principle $$$(\text{count}(r) - \text{count}(l-1))$$$, we efficiently find the global maximum length in $$$O(\log^2 r)$$$ time.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include <C:/Users/ajiit/Desktop/Future/Coding/Problem Solving/debug.cpp>
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 957483783; 
 
int calc(int n, int x) {
    if (x > n) return 0;
 
    int f = 0;
    for (int i=0;i<=60;i++) {
        if ((x >> i) & 1) continue;
        else f++;
    }
    
    int res = 0;
    for (int i=60;i>=0;i--) {
        int nb = (n >> i) & 1;
        int xb = (x >> i) & 1;
        
        if (!xb) {
            f--;
            if (nb) res += (1LL << f);
        } 
        else {
            if (!nb) return res;
        }
    }
    return res + 1;
}
 
void solve() {
    int l , r , k;
    cin >> l >> r >> k;
    
    vector<int> v;
    v.push_back(k);
    
    for (int i=0;i<=60;i++) {
        if ((k >> i) & 1) continue;
        else {
            int m = ~((1LL << i) - 1);
            int cur = (k | (1LL << i)) & m;
            if (cur <= r) v.push_back(cur);
        }
    }
    
    int ans = 0;
    for (int x : v) {
        if (x > r) continue;
        int cnt = calc(r, x) - calc(l - 1, x);
        ans = max(ans, cnt);
    }
    
    cout << ans % MOD << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

The core of this problem lies in recognizing that repeated prefix sums are equivalent to combinations with repetition. Starting from $$$S(0) = [1, 2, 3, \dots]$$$, where the $$$i$$$-th term is $$$S(0)[i] = i = \binom{i}{1}$$$, each subsequent level of prefix sums follows the Hockey-stick Identity:

Applying this property recursively, the $$$i$$$-th term of the $$$k$$$-th sequence is

To find the sum of elements from index $l$ to $$$r$$$, we calculate the prefix sum of $$$S(k)$$$ itself. Summing $$$S(k)[i]$$$ from $$$1$$$ to $$$N$$$ is equivalent to applying the identity once more:

Therefore, the sum from $$$l$$$ to $$$r$$$ is derived using the difference of prefix sums:

Since $$$k, l,$$$ and $$$r$$$ can be as large as $$$10^{18}$$$, and the result is required modulo a prime $$$p$$$, Lucas's Theorem is the optimal tool. It allows us to compute these large binomial coefficients in $$$O(p + q \log_p N)$$$ time by breaking the numbers into their base-$$$p$$$ digits. This approach successfully reduces a complex recursive sequence into a direct combinatorial evaluation.

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl "\n"
 
int mod;
 
int ma(int a, int b) {return (a%mod + b%mod + mod) % mod;}
int ms(int a, int b) {return (a%mod - b%mod + mod) % mod;}
int mm(int a, int b) {return (a%mod * b%mod) % mod;}
 
int modexp(int base, int exp) {
    int res = 1;
    base %= mod;
    while(exp) {
        if(exp & 1) res = mm(res, base);
        base = mm(base, base);
        exp >>= 1;
    }
    return res;
}
 
int modinv(int x) {
    return modexp(x, mod-2);
}
 
void solve()
{
    int q;
    cin >> mod >> q;
 
    // Precompute factorials only up to mod-1
    vector<int> fact(mod), invfact(mod);
 
    fact[0] = 1;
    for(int i = 1; i < mod; i++)
        fact[i] = mm(fact[i-1], i);
 
    invfact[mod-1] = modinv(fact[mod-1]);
    for(int i = mod-2; i >= 0; i--)
        invfact[i] = mm(invfact[i+1], i+1);
 
    auto comb = [&](int n, int r) -> int {
        if(n < 0 || r < 0 || r > n) return 0;
        return mm(fact[n], mm(invfact[n-r], invfact[r]));
    };
 
    auto lucas = [&](int n, int r) -> int {
        int ans = 1;
        while(n > 0 || r > 0) {
            ans = mm(ans, comb(n % mod, r % mod));
            n /= mod;
            r /= mod;
        }
        return ans;
    };
 
    while(q--) {
        int k,l,r;
        cin >> k >> l >> r;
 
        int right = lucas(r + k + 1, k + 2);
        int left  = lucas(l + k, k + 2);
 
        cout << ms(right, left) << endl;
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    solve();
}

The problem asks us to find the largest integer $$$y$$$ such that $$$x = a^y$$$ for some integer $$$a$$$. Since $$$x \le 10^{18}$$$ and $$$a \ge 2$$$, the maximum possible value for $$$y$$$ is $$$\lfloor \log_2(10^{18}) \rfloor \approx 60$$$. This small range for $$$y$$$ allows us to iterate through all possible exponents in descending order, from 60 down to 1. For a fixed exponent $$$i$$$, we need to determine if there exists an integer $$$a$$$ such that $$$a^i = x$$$. Because the function $$$f(a) = a^i$$$ is monotonically increasing for $$$a \ge 1$$$, we can efficiently check for the existence of $$$a$$$ using binary search in the range $$$[2, \sqrt[i]{x}]$$$.To prevent integer overflow during the calculation of $$$a^i$$$, we use a safe multiplication check ($$$t \gt \text{inf}/m$$$) before updating the product. The first (largest) $$$i$$$ that satisfies the condition $$$a^i = x$$$ is our answer. This approach runs in $$$O(\log(\text{max_exponent}) \cdot \log(\sqrt[i]{x}))$$$, which easily passes within the time limit given the constraints.

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl "\n"
 
bool TestCases = false;
int inf = 1e18;
 
bool check(int i,int n) {
    if(i==1) return true;
    int l = 2;
    int r = 1e9;
    while(l<=r) {
        int m = (l+r)/2;
        int t = 1;
        bool ok = true;
        for(int j=1;j<=i;j++) {
            if(t>inf/m) {
                ok = false; break;
            }
            t*=m;
            if(t>n) {
                ok = false; break;
            }
        }
        if(!ok) {
            r = m-1;
        }else if(t==n) {
            return true;
        }else {
            l = m+1;
        }
    }
    return false;
}
 
void solve()
{
    int n; cin>>n;
    for(int i=60;i>0;i--) {
        if(check(i,n)) {
            cout<<i;
            return;
        }
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t = 1;
    if(TestCases)
    {
        cin >> t;
    }
 
    while(t--)
    {
        solve();
    }
}

The game can be divided into two states based on the total sum:

1. Initial Sum is Even: Alice and Bob are locked into moves that maintain parity. An odd number must be replaced by an odd divisor, and an even number must be replaced by an even divisor. We calculate the Grundy value $$$G(u)$$$ for each number $$$u$$$ by considering only these "parity-preserving" divisors. The game then follows the Sprague-Grundy Theorem, where Alice wins if $$$G(a_1) \oplus G(a_2) \oplus \dots \oplus G(a_n) \neq 0$$$.

2. Initial Sum is Odd: Alice's first move must be parity-flipping to make the sum even. She must find an even $$$a[i]$$$ and replace it with an odd divisor $$$v$$$ such that the resulting game state (now with an even sum) is a losing position for Bob. This is possible if there exists some $$$a[i]$$$ and its odd divisor $$$v$$$ such that $$$G(v) = \text{XOR_sum} \oplus G(a[i])$$$. If no such move exists, Alice cannot even make a legal first move and loses immediately.

By precomputing Grundy values using a memoized $$$O(N \log N)$$$ sieve and checking these conditions, we determine the winner in $$$O(N + \sum \text{divisors})$$$ per test case.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include <C:/Users/ajiit/Desktop/Future/Coding/Problem Solving/debug.cpp>
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int MAXN = 1000005;
 
vector<int> divs[MAXN];
int memo[MAXN];
 
void pre() {
    for (int i = 1; i < MAXN; ++i) {
        for (int j = 2 * i; j < MAXN; j += i) {
            divs[j].push_back(i);
        }
    }
    memset(memo, -1, sizeof(memo));
}
 
int get_grundy(int u) {
    if (memo[u] != -1) return memo[u];
    
    int mask = 0;
    for (int v : divs[u]) {
        if (u % 2 != 0) {
            mask |= (1LL << get_grundy(v));
        } else {
            if (v % 2 == 0) {
                mask |= (1LL << get_grundy(v));
            }
        }
    }
    
    int g = 0;
    while ((mask >> g) & 1) g++;
    return memo[u] = g;
}
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> a(n);
    int par = 0;
    int xr = 0;
    
    for (int i=0;i<n;i++) {
        cin >> a[i];
        par = (par + a[i]) % 2;
        xr ^= get_grundy(a[i]);
    }
 
    if (par == 0) {
        if (xr > 0) cout << "Alice\n";
        else cout << "Bob\n";
    } 
    else {
        bool ok = false;
        for (int x : a) {
            if (x % 2 == 0) {
                int target = xr ^ get_grundy(x);
                for (int v : divs[x]) {
                    if (v % 2 != 0) {
                        if (get_grundy(v) == target) {
                            ok = true;
                            break;
                        }
                    }
                }
            }
            if (ok) break;
        }
 
        if (ok) cout << "Alice\n";
        else cout << "Bob\n";
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    pre();
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

Problem Overview: The problem requires us to deduce the hidden triangulation of a convex $$$N$$$-gon by querying the number of diagonals intersected by a given line segment. Given a query limit of $$$4000$$$ for $$$N \le 1000$$$, an $$$O(N^2)$$$ approach will fail. We present an $$$O(N)$$$ monotonic stack solution that uses at most $$$2N$$$ queries.

The Logic and Mathematical Proof:

We process vertices from $$$1$$$ to $$$N$$$ in clockwise order, maintaining a stack $$$S = [s_1, s_2, \dots, s_k]$$$ of vertices that form the “exposed” boundary of our discovered triangulation. When we visit vertex $$$i$$$, we check if $$$i$$$ can form a diagonal with $$$s_{k-1}$$$ (the vertex just below the top of the stack). We query the segment $$$(s_{k-1}, i)$$$.

Case 1: Query returns 0. If the segment $$$(s_{k-1}, i)$$$ crosses no diagonals, the region bounded by $$$s_{k-1}, s_k, i$$$ is completely empty. Since the polygon is fully triangulated, $$$\triangle s_{k-1}s_ki$$$ must be a triangle in the hidden triangulation. Furthermore, because diagonals cannot cross, no future vertex $$$j \gt i$$$ can ever connect to $$$s_k$$$ without crossing the newly discovered diagonal $$$(s_{k-1}, i)$$$. Thus, $$$s_k$$$ is “sealed off” and can be permanently popped from the stack.

Case 2: Query returns > 0. If $$$(s_{k-1}, i)$$$ is intersected by a hidden diagonal, that diagonal must originate from $$$s_k$$$ and connect to some future vertex $$$j \gt i$$$. Because the vertices are ordered cyclically on a convex hull, any line segment from $$$i$$$ to a deeper stack element $$$s_m$$$ ($$$m \lt k-1$$$) will also be strictly intersected by this diagonal from $$$s_k$$$. Therefore, $$$i$$$ cannot connect to any deeper stack elements. We halt our backward search, push $$$i$$$ to the stack, and move to the next vertex.

Complexity: Every query either results in popping an element from the stack or breaking the inner loop. Since exactly $$$N$$$ elements are pushed to the stack, there can be at most $$$N$$$ pops and $$$N$$$ loop breaks. Thus, the total number of queries is strictly bounded by $$$2N$$$, effortlessly passing the limit.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(int i=a; i<b; i++)
using vi=vector<int>;
using vii=vector<vi>;
using vpii=vector<pair<int,int>>;
#define pb push_back
 
int quer(int u, int v) {
    cout<<"? "<<u<<" "<<v<<endl;
    int ans; cin>>ans;
    if (ans==-1) exit(0);
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin>>n;
    vi st; vpii diag;
    st.pb(1); st.pb(2);
    FOR(i,3,n+1) {
        while (st.size()>=2) {
            int top=st.back();
            int pv=st[st.size()-2];
            int cut=0;
            if (pv==1 && i==n) {
              cut=0;
            }
            else {
                cut=quer(pv,i);
            }
            if (cut==0){
                if (!(pv==1 && i==n)){
                    diag.pb({pv,i});
                }
                st.pop_back();
            }
            else {
                break;
            }
        }
        st.pb(i);
    }
    cout<<"!"<<endl;
    FOR(i,0,size(diag)) {
        cout<<diag[i].first<<" "<<diag[i].second<<endl;
    }
    cout<<flush;
}