梅森数

描述：

形如2n−1的素数称为梅森数（Mersenne Number）。例如22−1=3、23−1=7都是梅森数。1722年，双目失明的瑞士数学大师欧拉证明了231−1=2147483647是一个素数，堪称当时世界上“已知最大素数”的一个记录。本题要求编写程序，对任一正整数n（n<20），输出所有不超过2n−1的梅森数。

输入格式：

输入在一行中给出正整数n（n<20）。

输出格式：

按从小到大的顺序输出所有不超过2n−1的梅森数，每行一个。如果完全没有，则输出“None”。

输入样例：

6

输出样例：

3

7

31

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7;
ll Prime[N+5];
bool isPrime[N+5];
int cnt = 0;
void GetPrime(ll n){
    memset(isPrime,1,sizeof(isPrime));
    isPrime[1] = 0;
    for(ll i = 2;i<=n;i++){
        if(isPrime[i]){
            Prime[++cnt] = i;
        }
        for(ll j=1;j<=cnt&&i*Prime[j]<=n;j++){
            isPrime[i*Prime[j]] = 0;
            if(i%Prime[j]==0)   break;
        }
    }
}
ll pow(ll a,ll b){
    ll ans = 1;
    ll base = a;
    while(b){
        if(b&1){
            ans*=base;
        }
        base*=base;
        b>>=1;
    }
    return ans;
}
int main(){
    ll n;
    scanf("%lld",&n);
    ll sum = pow(2,20);
    GetPrime(sum);
    int flag = 0;
    int i = 1;
    while(i<=n){
        ll num = pow(2,i);
        if(isPrime[num-1]){
            printf("%lld\n",num-1);
            flag = 1;
        }
        i++;
    }
    if(!flag){
        printf("None");
    }
    return 0;
}

解析：

首先构建素数表，并且再n之前，每一次得到2的n次方-1，从1开始，最后将满足条件的数字输出出来。或者直接判断，并不构建素数表，直接对每一个2的n次方-1的数字进行判断。

题解中使用的分别是欧拉筛和快速幂算法，正常写的时候只需要使用常用的判断素数和系统自带的POW即可。我在这里写主要是熟悉一下这两个算法。

高空坠球

描述：

皮球从某给定高度自由落下，触地后反弹到原高度的一半，再落下，再反弹，……，如此反复。问皮球在第n次落地时，在空中一共经过多少距离？第n次反弹的高度是多少？

输入格式：

输入在一行中给出两个非负整数，分别是皮球的初始高度和n，均在长整型范围内。

输出格式：

在一行中顺序输出皮球第n次落地时在空中经过的距离、以及第n次反弹的高度，其间以一个空格分隔，保留一位小数。题目保证计算结果不超过双精度范围。

输入样例：

33 5

输出样例：

94.9 1.0

代码：

#include<stdio.h>
int main()
{
    double high, sum = 0;
    int num;
    scanf("%lf %d",&high,&num);
    if(num==0)
        high = 0;
    while(num--){
        sum += high;
        high /= 2;
        sum += high;
    }
    printf("%.1lf %.1lf",sum-high,high);
    return 0;
}

解析：

首先特判一下第零次时候，其次将每一次的距离和反弹高度进行计算。这道题算法较为简单，解题的时候画图可以更好的理解。

一只小菜鸡