Codeforces 1343A - Candies

照片是随手拍的月亮，小米9的月亮模式一直没用明白，拍出的都是高糊的图片，我的摄影技术大概是没救了。这篇题解已经等了很久了，连续两天分别加班和吃饭，一天就在忙碌中度过。

题目: Codeforces 1343A - Candies
https://codeforces.com/problemset/problem/1343/A

翻译

总共买过 𝑛 块糖，第一天买 𝑥 块，第二天买 2𝑥 块，第三天买 4𝑥 块，第 𝑘 天买 2^𝑘-1，总共 𝑘 天，𝑘 > 1。

输入：

第一行输入 𝑡，接下来输入 𝑡 个 𝑛，可以保证至少有一对 x 和 k 可以使 𝑥+2𝑥+4𝑥+⋯+2^𝑘−1𝑥=𝑛 等式成立。

输出：

任意一个 𝑥，可以使等式成立。

分析

这个计算式经过计算 𝑥+2𝑥+4𝑥+⋯+2^𝑘−1𝑥 可以转换成 (1 + 2 + 4 + ⋯ + 2^𝑘−1)𝑥，进一步变成 (2^𝑘 - 1)𝑥，也就是要保证 (2^𝑘 - 1) 能被 𝑛 整除，其结果就是要输出的答案。而 𝑘 的值是有限的，口算小于32，每个 𝑛 需要计算 32 次 2^𝑘 - 1 的值能否整除，只要整除就可以输出，所以时间复杂度为 O(t * 32) 大概是 10⁵ 这个地方如果用用 C++ 还有个考点就是 快速幂 ，用python就可以省略了。

代码(Python3)

image.png

# https://codeforces.com/problemset/problem/1343/A

import math
import sys

# sys.stdin = open('in.txt', 'r')
# sys.stdout = open('out.txt', 'w')

t = int(input())
for index in range(t):
    n = int(input())
    k = 2
    while True:
        sum = int(math.pow(2, k) - 1)
        if n % sum == 0:
            break
        k += 1
    
    x = int(n / sum)
    print(x)

by 费城的二鹏 2020.04.30