Codeforces Round #636 A. Candies

May 14, 2020

問題

問題リンク

手元にキャンディの包み紙がn枚ある
わかっているのはキャンディを買い始めて、初日はx個、2日目は2x個、3日目は4x個、k日目は2^(k-1)を買ったこと

xに当てはまる数を答えろという問題

以下のことが保証されている

• x,k共に正の数かつ、k > 1
• 必ず条件を満たすx,kが存在する

考えたこと

2変数あるときは片方を固定してみると、解法が見えることがある.
仮にk=3とした場合

• n == x + 2x + 4x
• -> n == 7x

k=5とした場合は

• n == x + 2x + 4x + 8x + 16x
• -> n == 31x

という事になる。

ここから、2の累乗を足していって、その数でnが割れれば、xは正数になりそう.
2^30くらいで制約のn <= 10^9を超えてるので、そんなに計算量もかからない

あとはk > 1という制約を忘れないようにしよう(k == 1だと、x == nが答えになってしまう)

提出したコード

int main() {
    int t; cin >> t;
    rep(_, t) {
        ll n; cin >> n;
        // 2日目から始まるようにする(1 + 2 == 3)
        ll sum = 3;
        ll bi = 2;
        while(n%sum != 0) {
            bi *= 2;
            sum += bi;
        }
        // 割り切れたら、割った数=xである
        cout << n/sum << endl;
    }

    return 0;
}