梅森数
描述:
形如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;
}
解析:
首先特判一下第零次时候,其次将每一次的距离和反弹高度进行计算。这道题算法较为简单,解题的时候画图可以更好的理解。
Comments | NOTHING