赞
踩
3.质因数的个数
时间限制:1000MS
内存限制:65536KB
题目描述:
因数:又称为约数,如果整数a除以整数b(b!=0)的商正好是整数且没有余数,我们就说b是a的因数。
质数:又称为素数,一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数。2时最小的质数。
质因数:如果一个属a的因数b同时页数质数,娜美b就是a的一个质因数。
题目描述:
给定两个正整数N和M(1<=N<=M<=1e7),统计N到M之间(含N和M)每个数所包含的质因数的个数,输出其中最大的个数
输入描述:输入两个正整数N和M,两个正整数之间用一个空格隔开
输出描述:输出一个整数,表示质因数个数的最大值
样例输入:6 10
样例输出:3
#include <bits/stdc++.h>
using namespace std;int f (int o) {//定义了一个用来判断当前数最大质因数的函数
int c = 1, k = 0;
while (o != 1) {
for (int i = 2; i <= sqrt(o); i++) {
if (o % i == 0) {
c++;
k = i;
break;
}
}
o /= k;
}
return c;
}int main() {
int maxn = 0, n, m;
cin >> n >> m;
for (int i = n; i <= m; i++) {
if (f(i) >= maxn)
maxn = f(i);
}
cout << maxn;
return 0;
}
4.最大的矩形纸片
时间限制:1000ms
内存限制:65535KB
题目描述:
一张半边参差不齐的网格纸(网格边长均为1),有一边是完整没有破碎的。现在要从中剪出一篇面积最大的矩形纸片
给定网格纸中完整边的长度为N(1<=n<=1000000),以及网格中每一列残存部分的高度(1<=高度<=10000),输出能够剪出的最大的矩形纸片面积
输入描述:第一行输入一个正整数N(1<=n<=1000000),表示纸片完整边的长度,第二行输入N个正整数(1<=正整数<=10000),表示每列格子残存部分的高度,两个正整数之间用一个空格隔开
输出描述:输出一个正整数,表示能够剪出的最大矩形纸片的面积
样例输入:
6
3 2 1 4 5 2
样例输出:
8
#include <bits/stdc++.h>
using namespace std;const int N = 1000010;
int h[N], z[N], y[N], n, maxn = 0, s;int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
z[i] = i; //左边界
y[i] = i; //右边界
}//初始化左右边界
//求所有悬线的左边界
for (int i = 1; i <= n; i++) {
while (z[i] > i && h[i] <= h[z[i] - 1]) { //z[i]-1为左边界前一项
z[i] = z[z[i] - 1]; //继承前一项的左边
}
}
//求所有悬线的右边界
for (int i = 1; i <= n; i++) {
while (y[i] < n && h[i] <= h[y[i] + 1]) { //y[i]+1为右边界后一项
y[i] = y[y[i] + 1]; //继承后一项的右边
}
}
//打擂台
for (int i = 1; i <= n; i++) {
s = h[i] * (y[i] - z[i] + 1);
maxn = max(s, maxn);
}
cout << maxn;
return 0;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。