P9779 [HUSTFC 2023] 不定项选择题 题解

· · 题解

P9779 [HUSTFC 2023] 不定项选择题 题解

题意简述

给你一个选择题，并告诉你共 n 个选项，在最坏情况下要试几次才能做对这道题。

分析

一眼简单数论题。对于每个选项，你可以选它，也可以不选它，每个选项就有两种可能的选择情况。由于 n 个选项在最坏情况下每个都要试一下，视为总共有 n 个步骤，则根据乘法原理，总次数为 n 个 2 相乘，总共就是 2^n 种情况，去掉不选任何一个选项的情况（想要做对肯定不能交白卷），则最终答案为 2^n -1。

代码

二进制位移写法

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    cout<<(1<<n)-1;
    return 0;
}

普通写法

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int ans=1;//ans=1是因为要进行连乘
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       ans*=2; 
    }
    cout<<ans-1;
    return 0;
}

快速幂写法

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int qpow(int a,int b)//快速幂模板
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
signed main()
{
    cin>>n;
    cout<<qpow(2,n)-1;
    return 0;
}