Codeforces_forever Round #3 (Div4) B

Заметим, что
k−1
∑
i=0 2i=2k−1. Поэтому мы можем заменить изначальное уравнение следующим: (2k−1)x=n. Итак, мы можем перебрать все возможные k в отрезке [2;29] (потому что 230−1>109) и проверить, делится ли n на 2k−1. Если делится, то мы можем вывести x=
n
2k−1

.

P.S. Я знаю, что много участников нашли формулу
k−1
∑
i=0 2i=2k−1, используя формулу суммы геометрической прогрессии, но есть другой путь понять это, и он намного более интуитивен, по крайней мере для меня. Просто посмотрим на двоичные представления чисел: можно заметить, что 20=1,21=10,22=100, и так далее. Поэтому 20=1,20+21=11,20+21+22=111, и так далее. И если мы добавим единицу к этому числу, состоящему из k единиц, то мы получим 2k.
#include <bits/stdc++.h>
#define int int64_t
#define double long double
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back();
#define ppf pop_front();
#define For(n) for (int i = 0; i < n; i++)
#define FOR(i, n) for (i; i < n; i++)
#define optimization ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef pair <int, int> pii;
typedef deque <int> di;

int binpow(int x, int y)
{
    if (y == 0)
        return 1;
    if (y & 1)
        return binpow(x, y - 1) * x;
    else
    {
        int ans = binpow(x, y / 2);
        return ans * ans;
    }
}

int32_t main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int sum = 3, prsum = 4;
        while (n % sum)
        {
            sum += prsum;
            prsum *= 2;
        }
        cout << n / sum << "\n";
    }
}