1928C - Physical Education Lesson

 Physical Education Lesson

Algorithm Used: Math

Let's define a cycle as the first 2k - 2 people since the settling repeats every 2k - 2 people. In order for a person to be seated at the xth position, they need to be either the xth person in the cycle or the (2k - x)th person in the cycle. Therefore if we decide that the nth person will occupy the xth position in the cycle, then

n = (2k-2) * t + x; where t is the number of cycles that have passed

n - x = (2k-2) * t

Clearly in order for this equation to have an answer (2k-2) must be an even factor of n - x. to find the solutions to this equation, therefore we only need to count the number of factors of n - x that are even and are greater than or equal to x.

If we decide that the nth person will occupy the (2k - x)th position in the cycle, then 

n = (2k - 2) * t + 2k - x;

n + x = (2k - 2) * t + 2k

n + x - 2 = (2k - 2) * t + 2k - 2

n + x - 2 = (2k - 2)(t + 1)

In order for this equation to be satisfied, (2k - 2) must be an even factor of n + x - 2 and be greater than or equal to x.

Code

#include <iostream>

#include <vector>

#include <set>

using namespace std;

using ll = long long;

set <int> factors;

void get_factors(ll a) {

    for (ll i = 1; i * i <= a; i++) {

        if (a % i == 0) {

            if (i % 2 == 0)

                factors.insert((i + 2) / 2);

            if (a / i != i && (a / i) % 2 == 0)

                factors.insert((a / i + 2) / 2);

        }

    }

}

int main() {

    int T;

    cin >> T;

    while (T--) {

        ll n, x;

        cin >> n >> x;

        factors.clear();

        get_factors(n - x);

        get_factors(n + x - 2);

        int ans = 0;

        for (auto i : factors) {

            if (i >= x)

                ans++;

        }        

        cout << ans << '\n';

    }

}