CodeForces - 1343A - Candies

链接：https://codeforc.es/contest/1343/problem/A

原题

Recently Vova found nn candy wrappers. He remembers that he bought x candies during the first day, 2x candies during the second day, 4x candies during the third day, ……, 2k−1x candies during the k-th day. But there is an issue: Vova remembers neither x nor k but he is sure that xx and kk are positive integers and k>1. Vova will be satisfied if you tell him any positive integer xx so there is an integer k>1 that x+2x+4x+⋯+2k−1x=n. It is guaranteed that at least one solution exists. Note that k>1. You have to answer tt independent test cases. InputThe first line of the input contains one integer tt (1≤t≤104) — the number of test cases. Then tt test cases follow. The only line of the test case contains one integer nn (3≤n≤109) — the number of candy wrappers Vova found. It is guaranteed that there is some positive integer xx and integer k>1 that x+2x+4x+⋯+2k−1x=n.OutputPrint one integer — any positive integer value of x so there is an integer k>1 that x+2x+4x+⋯+2k−1x=n.Example

Input

7 3 6 7 21 28 999999999 999999984

Output

1 2 1 7 4 333333333 333333328

题意

第1天找到x个糖果，第2天找到2x个糖果，第三天找到4x个糖果，……第k天找到2的k-1次方x个糖果，总共找到n个糖果，存在正整数x和k，给出一个n，输出一个x值。

**

思路

(1+2+4+……+2^k-1)x=n 前面括号里是等比数列求和，括号里等于 2^k-1， 所以(2^k-1)x=n。 从2开始枚举k，看n能否被2^k-1整除。若能，则输出n/(2^k-1)的结果x；若不能，则k++继续判断。

代码

#include<iostream> using namespace std; int t; int main() { long long int n,x,a; cin>>t; while(t--) { a=3; cin>>n; if(n%a==0) x=n/a; while(n%a!=0) { a=(a+1)*2-1; if(n%a==0) x=n/a; } cout<<x<<endl; } return 0; }