CodeForces1343A - Candies - 等比数列推导

PS：这题怎么也不像的A题，而且还是div3耶，一点也不像900分的题，啊，我菜死了。

题目链接：https://codeforces.com/contest/1343/problem/A

题意：
要求求出该公式中\(x\)的值（已知\(k>1\)）。
x+2 x+4 x+\cdots+2^{k-1} x=n

首先来说明一下等比数列求和的公式：

\(S_{n}=n \times a_{1} \quad(q=1)\)

\(S_{n}=a_{1} \cdot \frac{1-q^{n}}{1-q}=\frac{a_{1}-a_{n} \cdot q}{1-q} \quad(q \neq 1)\)

思路：
把题目给的公式提取公因式，变形为\(x(1+2+4+...+(2k-1))=n\)。
因为同时涉及到\(x%=\)和\(k\)，
所以利用\(S_{n}=\frac{a_{1}-a_{n} \cdot q}{1-q} \quad(q \neq 1)\)这个公式进行化简，
化简后可得\(x\times{2^{k}-1}=n\)。
因为x是正整数，\(k>1\)，
所以通过\(n%{2^{k}-1}==0就可以判断此时可以取到\)x\(，从而得出结果\)。

因为\(2^{10}=1024\)，\(2^{30}=10^9\)，
给的数据范围最大是\(10^9\)，所以直接暴力枚举k的值从而求得\(x\)的值并不会超时。

AC代码（C++）：

#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int k=2;;k++)
        {
            int q=(int)pow(2,k)-1;
            if(n%q==0)
            {
                cout<<n/q<<endl;
                break;
            }
        }
    }
    return 0;
}

AC代码（Python）：

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)

CodeForces1343A - Candies - 等比数列推导

原文：https://www.cnblogs.com/OFSHK/p/13197384.html