Codeforces--630C--Lucky Numbers（快速幂）

C -
Lucky Numbers

Crawling in process...
Crawling failed
Time Limit:500MS
Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Submit
Status

Description

The numbers of all offices in the new building of the Tax Office of IT City will have lucky numbers.

Lucky number is a number that consists of digits 7 and
8 only. Find the maximum number of offices in the new building of the Tax Office given that a door-plate can hold a number not longer than
n digits.

Input

The only line of input contains one integer n (1 ≤ n ≤ 55) — the maximum length of a number that a door-plate can hold.

Output

Output one integer — the maximum number of offices, than can have unique lucky numbers not longer than
n digits.

Sample Input

Input

Output

数字中只含有7或者8的成为Lucky Numbers，问n位以内的数字有多少个Lucky Numbers，总数应该就是2+2^2+....+2^n,数学公式变形之后就是2^(n+1)-2个，n+1可能比较大，所以快速幂解决

#include<iostream>

using namespace std;

#define LL long long

LL  p(LL x, LL n)

{

    LL pw = 1;

    while (n > 0)

    {

        if (n & 1)

            pw *= x;

        x *= x;

        n >>= 1;

    }

    return pw;

}

int main()

{

    LL n;

    LL num;

    cin>>n;

    cout<<p(2,n+1)-2<<endl;

    return 0;

}

巴特西

Codeforces--630C--Lucky Numbers（快速幂）

最新文章

热门文章