梅森数

描述:

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

输入格式:

输入在一行中给出正整数nn<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;
}

解析:

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


一只小菜鸡