#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        vector < vector <int> > b(k);
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            b[x % k].push_back(i);
        }
        int res = -1;
        for (int i = 0; i < k; i++) {
            if ((int)b[i].size() == 1) {
                res = b[i][0];
                break;
            }
        }
        if (res == -1) {
            cout << "NO" << endl;
        }
        else {
            cout << "YES" << endl << res << endl;
        }
    }
    
    return 0;
}

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = [[] for _ in range(k)]
    for i in range(0, n):
        x = a[i]
        b[x % k].append(i + 1)
    res = -1
    for i in range(k):
        if len(b[i]) == 1:
            res = b[i][0]
            break
    if res == -1:
        print("NO")
    else:
        print("YES\n" + str(res))

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        for (int ans = 1, cur = 1; ; ans++, cur = cur * 2 + 2) {
            if (cur >= n) {
                cout << ans << '\n';
                break;
            }
        }
    }
    
    return 0;
}

tt = int(input())
for _ in range(tt):
    n = int(input())
    ans = 1
    cur = 1
    while True:
        if cur >= n:
            print(ans)
            break
        ans += 1
        cur = cur * 2 + 2

В какой-то момент разработки этой задачи появилось следующее альтернативное условие: нам необходимо минимизировать общее количество операций обоих типов. Как решить эту задачу?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        long long k;
        cin >> n >> k;
        vector <int> a, b;
        
        if (n <= 60 && (1ll << (n - 1)) < k) {
            cout << -1 << endl;
            continue;
        }
        k--;
        vector <int> d;
        while (k) {
            d.push_back(k % 2);
            k /= 2;
        }
        while (d.size() < n - 1) d.push_back(0);
        
        for (int i = n - 2, j = 1; i >= 0; i--, j++) {
            if (d[i] == 0) a.push_back(j);
            else b.push_back(j);
        }
        
        reverse(b.begin(), b.end());
        for (int i : a) cout << i << ' ';
        cout << n << ' ';
        for (int i : b) cout << i << ' ';
        cout << endl;
    }
 
    return 0;
}

tt = int(input())
for _ in range(tt):
    n, k = map(int, input().split())
    a, b = [], []
 
    if n <= 60 and (1 << (n - 1)) < k:
        print(-1)
        continue
    k -= 1
    d = []
    while k:
        d.append(k % 2)
        k //= 2
    while len(d) < n - 1:
        d.append(0)
 
    a, b = [], []
    j = 1
    for i in range(n - 2, -1, -1):
        if d[i] == 0:
            a.append(j)
        else:
            b.append(j)
        j += 1
 
    b.reverse()
    print(*a, n, *b)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector < vector <int> > g(n);
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        vector <int> res(n);
        int lst = 1;
        res[0] = lst;
        
        function <void(int, int)> dfs = [&](int v, int p) {
            for (int to : g[v]) {
                if (to == p) continue;
                res[to] = lst + 1;
                while (res[to] != res[v] + 1 && 
                      (res[to] % 2 != res[v] % 2 || res[to] - res[v] == 2)) {
                    res[to]++;   
                }
                lst = res[to];
                dfs(to, v);
            }
        };
        
        dfs(0, 0);
        for (int i : res) cout << i << ' ';
        cout << endl;
    }
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
void dfs(int v, vector<vector<int>>& g, vector<int>& h, int p) {
    h[v] = h[p] + 1;
    for (int u : g[v]) {
        if (u == p)
            continue;
        dfs(u, g, h, v);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int> h(n);
        dfs(0, g, h, 0);
        vector<vector<int>> hs(n + 1);
        for (int i = 0; i < n; i++)
            hs[h[i]].push_back(i);
        int l = 2, r = 2 * n;
        int cur = 0;
        vector<int> ans(n);
        for (int i = 1; i <= n; i++) {
           if (cur) {
               for (int v : hs[i]) {
                    ans[v] = r;
                    r -= 2;
               }
           } 
           else {
               for (int v : hs[i]) {
                    ans[v] = l;
                    l += 2;
               }
           }
           cur ^= 1;
        }
        bool found = false;
        for (int i = 0; i < n; i++) {
            for (int v : g[i]) {
                if (h[v] < h[i])
                    continue;
                if (abs(ans[v] - ans[i]) == 2) {
                    ans[v] = ans[i] - 1;
                    found = true;
                    break;
                }
            }
            if (found)
                break;
        }
        for (int i = 0; i < n; i++)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    
    return 0;
}

Существует множество возможных решений этой проблемы, и почти все тестировщики реализовали уникальное решение. Есть решения, правильность которых мы не смогли доказать, но и взломать их тоже не смогли.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
    
    vector < vector <int> > g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    vector <int> depth(n);
    vector <int> d(n);
    vector <int> par(n);
 
    function <void(int, int)> dfs = [&](int v, int p) {
        if (depth[v] == 1) d[v] = 1;
        if (depth[v] > 1) d[v] = d[par[p]] + 2 * (int)g[p].size();
        par[v] = p;
        for(int to : g[v]) {
            if (to == p) continue;
            depth[to] = depth[v] + 1;
            dfs(to, v);
        }
    };
    
    dfs(0, 0);
    
    while (q--) {
        int v, p;
        cin >> v >> p;
        v--;
        int res = d[v];
        vector <int> cnt;
        while (v != 0 && par[v] != 0) {
            cnt.push_back((int)g[par[v]].size());
            v = par[par[v]];
        }
        sort(cnt.rbegin(), cnt.rend());
        for (int i = 0; i < min(p, (int)cnt.size()); i++) {
            res -= 2 * (cnt[i] - 1);
        }
        cout << res << '\n';
    }
}
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
    
    vector < vector <int> > g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    vector <int> depth(n);
    vector <int> d(n);
    vector < vector < pair <int,int> > > qrs(n); // <p, idx>
    vector <int> res(q);
    
    for (int i = 0; i < q; i++) {
        int v, p;
        cin >> v >> p;
        v--;
        qrs[v].push_back({p, i});
    }
    
    multiset <int> st[2]; // store negative number to be able to use usual foreach loop
    
    function <void(int, int, int)> dfs = [&](int v, int p, int pp) {
        if (depth[v] == 1) d[v] = 1;
        if (depth[v] > 1) d[v] = d[pp] + 2 * (int)g[p].size();
        
        for (pair <int, int> qr : qrs[v]) {
            int p = qr.first, idx = qr.second;
            int ans = d[v];
            for (int i : st[1 - depth[v] % 2]) {
                if (p == 0) break;
                ans -= (-i - 1) * 2;
                p--;
            }
            res[idx] = ans;
        }
        
        if (depth[v] != 0) st[depth[v] % 2].insert(-(int)g[v].size());
        
        for (int to : g[v]) {
            if (to == p) continue;
            depth[to] = depth[v] + 1;
            dfs(to, v, p);
        }
        
        if (depth[v] != 0) st[depth[v] % 2].erase(st[depth[v] % 2].find(-(int)g[v].size()));
    };
    
    dfs(0, 0, 0);
    
    for (int i = 0; i < q; i++)
        cout << res[i] << '\n';
}
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

Изначально эта задача имела следующие ограничения:

1. $$$1 \le n, q \le 2 \cdot 10^5$$$

2. Сумма $$$p$$$ во всех запросах не больше $$$2 \cdot 10^5$$$

Как решить эту задачу?

Могли бы вы решить эту задачу и без второго ограничения?

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N], phi[N];
 
int powmod(int a, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            a = (a * a) % mod;
            n /= 2;
        }
        else {
            res = (res * a) % mod;
            n--;
        }
    }
    return res;
}
 
int inv(int a) {
    return powmod(a, mod - 2);
}
 
void prepare() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    ifact[N - 1] = inv(fact[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
    }
 
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        phi[i] = i - 1;
    }
    for (int i = 2; i < N; i++) {
        for (int j = i * 2; j < N; j += i) {
            phi[j] -= phi[i];
        }
    }
}
 
int C(int n, int k) {
    return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
 
int MC(vector <int> &a) {
    int sum=0;
    for (int i : a) sum += i;
    int res = fact[sum];
    for (int i : a) {
        res = (res * ifact[i]) % mod;
    }
    return res;
}
 
int lcm(int a, int b) {
    return a / __gcd(a, b) * b;
}
 
vector <int> all_divs(int x) {
    vector <int> d;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d.push_back(i);
            if (i * i != x) {
                d.push_back(x / i);
            }
        }
    }
    return d;
}
 
void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    vector <int> v(k);
    for (int &i : v) cin >> i;
 
    int g = v[0];
    for (int i : v) g = __gcd(g, i);
 
    map <int, int> mp;
    for (int i : all_divs(a)) {
        for (int j : all_divs(b)) {
            for (int l : all_divs(c)) {
                int N = lcm(i, lcm(j, l));
                if (g % N == 0) {
                    mp[N] += phi[i] * phi[j] * phi[l];
                }
            }
        }
    }
 
    int sum = 0;
    for (pair <int, int> pr : mp) {
        int N = pr.first, cnt = pr.second;
        vector <int> u;
        for (int t : v) u.push_back(t / N);
        sum = (sum + (MC(u) * cnt) % mod) % mod;
    }
 
    sum = (sum * inv(a * b * c)) % mod;
 
    cout << sum << endl;
}
 
int32_t main() {
    prepare();
 
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N];
int pos[N];
 
int powmod(int a, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            a = (a * a) % mod;
            n /= 2;
        }
        else {
            res = (res * a) % mod;
            n--;
        }
    }
    return res;
}
 
int inv(int a) {
    return powmod(a, mod - 2);
}
 
void prepare() {
    fact[0] = 1;
    for (int i = 1;i < N; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    ifact[N - 1] = inv(fact[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
    }
}
 
int C(int n, int k) {
    return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
 
int MC(vector <int> &a) {
    int sum=0;
    for (int i : a) sum += i;
    int res = fact[sum];
    for (int i : a) {
        res = (res * ifact[i]) % mod;
    }
    return res;
}
 
int lcm(int a, int b) {
    return a / __gcd(a, b) * b;
}
 
vector <int> all_divs(int x) {
    vector <int> d1, d2;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d1.push_back(i);
            if (i * i != x) {
                d2.push_back(x / i);
            }
        }
    }
    reverse(d2.begin(), d2.end());
    for (int i : d2) d1.push_back(i);
    return d1;
}
 
void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    vector <int> v(k);
    for (int &i : v) cin >> i;
 
    int g = v[0];
    for (int i : v) g = __gcd(g, i);
    vector <int> divs_g = all_divs(g);
 
    set <int> divs;
    for (int i : all_divs(a)) divs.insert(i);
    for (int i : all_divs(b)) divs.insert(i);
    for (int i : all_divs(c)) divs.insert(i);
    for (int i : all_divs(g)) divs.insert(i);
    int D = divs.size();
    int i = 0;
    for (int j : divs) {
        pos[j] = i;
        i++;
    }
 
    int n = max({a, b, c}) + 1;
    vector < vector <int> > tmp(3, vector <int> (D));
    vector < vector <int> > cnt(3, vector <int> (D));
    for (int t = 0; t < 3; t++) {
        int x;
        if (t == 0) x = a;
        if (t == 1) x = b;
        if (t == 2) x = c;
        vector <int> divs_x = all_divs(x);
 
        for (int i = (int)divs_x.size() - 1; i >= 0; i--) {
            tmp[t][pos[divs_x[i]]] += x / divs_x[i];
            for (int j = 0; j < i; j++) {
                if (divs_x[i] % divs_x[j] == 0) {
                    tmp[t][pos[divs_x[j]]] -= tmp[t][pos[divs_x[i]]];
                }
            }
            cnt[t][pos[x / divs_x[i]]] = tmp[t][pos[divs_x[i]]];
        }
    }
        
    vector < vector <int> > dp(4, vector <int> (D));
    dp[0][0] = 1;
    for(int i = 0; i < 3; i++) {
        for (int t1 : divs_g) {
            for (int t2 : divs_g) {
                int new_pos = lcm(t1, t2);
                if (t2 < n) {
                    dp[i + 1][pos[new_pos]] = (dp[i + 1][pos[new_pos]] + dp[i][pos[t1]] * cnt[i][pos[t2]]) % mod;
                }
            }
        }
    }
 
    int sum = 0;
    i = 0;
    for (int j : divs) {
        if (g % j != 0) continue;
        int N = j, cnt = dp[3][pos[j]];
        vector <int> u;
        for (int t : v) u.push_back(t / N);
        sum = (sum + (MC(u) * cnt) % mod) % mod;
    }
 
    sum = (sum * inv(a * b * c)) % mod;
 
    cout << sum << endl;
}
 
int32_t main() {
    prepare();
 
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}