Bài 91. Số P là số Mersenne nếu P nguyên tố và P = 2n – 1, mà n cũng là số nguyên tố.
a) Kiểm tra có số Mersenne trong dãy các phần tử mảng A nguyên dương hay không, nếu có liệt kê các phần tử đó.
b) Tìm các số Mersenne nhỏ hơn hoặc bằng kích thước mảng A.(so phan tu mang)
c) Tìm các số Mersenne nằm trên đoạn [n, P] với P là số Mersenne lớn nhất của dãy A và n là số mũ tương ứng của P = 2n – 1
Vd: input file cb91.txt 3 7 31 127 31 131 11 227 1111 1023 1999 23 67 87 101 47 61 73 83 57 37 531 71 27 2047 13 8191 17 131071 19 524287 23 8388607 29 536870911 311 2147483647 37 137438953471 41 2199023255551
Output: file KQcb91.txt
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <math.h>
#include <algorithm>
using namespace std;
bool snt(int nt){// /*sai khi gap tich 2 nguyen to vd: 77, 91.*/
if(nt<2) return false;
if(nt==2) return true;
if (nt==3)return true;
if(nt==5)return true;
if(nt%2==0) return false;
if(nt%3==0) return false;
if(nt%5==0) return false;
if((nt+1)%6==0) return true;
if((nt-1)%6==0) return true;
return false;
}
int mersenne(int qi){
if(!snt(qi)) return 0;
int q=qi+1;
int k=1;
while (q >= (1 << k)) {
k++;
}k--;
if(q==(1 << k)&&snt(k)) return k;
return 0;
}
int main(int argc, char** argv) {
cout << "Chuong trinh so Mersener \n";
ifstream fin("cb91.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file cb91.txt\n";
return 0;
}
vector<int> vo, tmp;
long int x;
while(fin >> x){
if(abs(x) > 1e15||x<=0) {
cerr << "so " << x << " khong hop le \n";
fin.clear();
continue;
}
vo.push_back(x);
}
fin.close();
if(vo.empty()) {
cerr<<"Khong co Data hop le";
return 0; }
int nP=vo.size();
for(auto P:vo){
if(mersenne(P)>0){
tmp.push_back(P);
}
}
if(tmp.empty()){
cout<<"Khong co so Mersenne trong day so \n";}
else {
cout<<"Cac so Mersenne trong day so la: \n";
for(auto c:tmp) cout<<c<<" ";
}cout<<"\n";
cout<<"Cac so Mersenne <= "<<nP <<" la: \n";
for(int i=2;i<=nP;i++){
if(mersenne(i)>0) cout<<i<<" ";
}cout<<"\n";
sort(tmp.begin(),tmp.end());
cout<<"So mu tuong ung voi so Mersenne trong day da cho la: \n";
for(auto c:tmp){
int n=mersenne(c);
cout<<"So mersenne "<<c<<" co so mu cua 2 tuong ung la:"<<n<<"\n";
}
ofstream fout("KQcb91.txt");
if(tmp.empty()){
fout<<"Khong co so Mersenne trong day so \n";}
else {
fout<<"Cac so Mersenne trong day so la: \n";
for(auto c:tmp) fout<<c<<" ";
}fout<<"\n";
fout<<"Cac so Mersenne <= "<<nP <<" la: \n";
for(int i=2;i<=nP;i++){
if(mersenne(i)>0) fout<<i<<" ";
}fout<<"\n";
fout<<"So mu tuong ung voi so Mersenne trong day da cho la: \n";
for(auto c:tmp){
int m=mersenne(c);
fout<<"So mersenne "<<c<<" co so mu cua 2 tuong ung la:"<<m<<"\n";
}
fout.close();
}
Chú ý:
Số nguyên tố Mersenne: là số Mersenne mà bản thân nó cũng nguyên tố. 2047 không phải nguyên tố (vì ), nên nó không phải số nguyên tố Mersenne.
ü Số Mersenne: với nguyên tố.
ü Số nguyên tố Mersenne: là số Mersenne mà bản thân nó cũng nguyên tố. Ví dụ: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647…
Định nghĩa: Số Mersenne có dạng với là số nguyên tố. Không phải mọi đều là số nguyên tố, nhưng chúng vẫn là số Mersenne.
Trong C/C++ khi dùng pow(2, k) thì hàm pow nằm trong thư viện <math.h> (C) hoặc <cmath> (C++).
Hoặc nếu chỉ cần tính lũy thừa của 2 thì có thể dùng toán tử dịch bit cho nhanh và gọn hơn: 1 << k tương đương với . Ví dụ:
while (q >= (1 << k)) {
// ...
}
Trong C++ có vài cách để tìm giá trị lớn nhất trong một container như tmp:
1. Dùng std::max_element
#include <algorithm>
#include <vector>
std::vector<int> tmp = {3, 7, 2, 9, 5};
int Pm = *std::max_element(tmp.begin(), tmp.end());
2. Dùng std::sort
#include <algorithm>
#include <vector>
std::vector<int> tmp = {3, 7, 2, 9, 5};
std::sort(tmp.begin(), tmp.end());
int Pm = tmp.back();
3. Tự duyệt vòng lặp
int Pm = tmp[0];
for (int x : tmp) {
if (x > Pm) Pm = x;
}
Hàm kiểm tra nguyên tố chuẩn:
bool snt(int nt) {
if (nt < 2) return false;
for (int i = 2; i <= sqrt(nt); i++) {
if (nt % i == 0) return false;
}
return true;
}
//////////////////////////////////////
Cách 2. Phiên bản rút gọn, tối ưu hơn:
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
bool snt(long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
int mersenne(long long qi) {
if (!snt(qi)) return 0;
long long q = qi + 1;
int k = 0;
while ((1LL << k) < q) k++;
if ((1LL << k) == q && snt(k)) return k;
return 0;
}
int main() {
cout << "Chuong trinh so Mersenne\n";
ifstream fin("cb91.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file cb91.txt\n";
return 0;
}
vector<long long> vo, tmp;
long long x;
while (fin >> x) {
if (x <= 0 || x > 1e15) {
cerr << "So " << x << " khong hop le\n";
continue;
}
vo.push_back(x);
}
fin.close();
if (vo.empty()) {
cerr << "Khong co Data hop le\n";
return 0;
}
for (auto P : vo) {
if (mersenne(P) > 0) tmp.push_back(P);
}
sort(tmp.begin(), tmp.end());
if (tmp.empty()) {
cout << "Khong co so Mersenne trong day so\n";
} else {
cout << "Cac so Mersenne trong day so la:\n";
for (auto c : tmp) cout << c << " ";
cout << "\nSo mu tuong ung:\n";
for (auto c : tmp) cout << "So " << c << " co mu " << mersenne(c) << "\n";
}
ofstream fout("KQcb91tu.txt");
if (tmp.empty()) {
fout << "Khong co so Mersenne trong day so\n";
} else {
fout << "Cac so Mersenne trong day so la:\n";
for (auto c : tmp) fout << c << " ";
cout << "\nSo mu tuong ung:\n";
for (auto c : tmp) fout << "So " << c << " co mu " << mersenne(c) << "\n";
}
}
Chú ý:
while ((1LL << k) < q) k++; hoạt động như sau:
- 1LL << k nghĩa là dịch bit sang trái, tức là tính .
- Vòng lặp sẽ tăng k cho đến khi .
- Khi thoát vòng lặp, ta có tình huống:
Nếu thì đúng bằng giá trị cần tìm.
Nếu thì k đã vượt, không hợp lệ, loại bỏ.
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love11.07.2026
///////////////////
Bài 92. Con ốc sên. Con ốc sên đang ở gốc một cái cây cao v mét tính từ gốc. Ốc sên muốn bò lên ngọn cây để ăn những lá non trên đó. Ban ngày ốc sên bò được a mét lên trên, nhưng ban đêm khi ngủ nó bị trôi xuống b mét.
Yêu cầu: Cho các số nguyên a, b, v (1 <= b < a <= v <= 109). Hãy xác định số ngày cần thiết để ốc sên lên tới ngọn cây. Ví dụ:
Cb92.txt | KQcb92.txt |
2 1 5 | 4 |
Gợi ý:
#include <bits/stdc++.h>
using namespace std;
int main (){
long long a, b, v;
cin >> a>> b >> v;
if (a==v) cout << 1;
else
{
if ((v-b)%(a-b)==0)
cout<<(v-b)/(a-b);
else cout<<(v-b)/(a-b) +1;
}
return 0;
}
Bài 93. Tìm một số nguyên dương k nhỏ nhất sao cho tích các chữ số của k bằng 2<=n<=10000000 (k, n là 2 số nguyên dương).
cb93.txt | Kqcb93.txt |
720 | 2589 ( 2.5.8.9 = 720) |
Gợi ý code:
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(int argc, char** argv) {
cout << "Chuong trinh tim so nho nhat co tich cac so bang N \n";
ifstream fin("cb93.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file cb93.txt\n";
return 0;
}
vector<int> vo;
int x;
fin >> x;
if((abs(x) > 1e7)||x<2) {
cerr << "so " << x << " khong hop le \n";
return 0;
}
fin.close();
int n=x,y=0;
for (int i=9;i>1;i--){
while(n%i==0){
n=n/i;
vo.push_back(i);
}
}sort(vo.begin(),vo.end());
if(n>1) {
cout<<"Khong tim duoc so thoa man \n";
return 0;
} for(int c:vo){
y=y*10+c;
} cout<<"So nho nhat co tich bang "<< x<< " la: "<<y<<" \n";
ofstream fout("Kqcb93.txt");
if(n>1) {
fout<<"Khong tim duoc so thoa man \n";
}else fout<<"So nho nhat co tich bang "<< x<< " la: "<<y<<" \n";
fout.close();
return 1;
}
//////////////////////
Cách 2
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream fin("cb93.txt"); // Mở file input
ofstream fout("Kqcb93c2.txt"); // Mở file output
int n, a = 0;
fin >> n;
for(int i = 9; i > 1; i--) {
while(n % i == 0 && n > 1) {
a = a * 10 + i;
n = n / i;
}
}
int b = 0;
while(a > 0) {
int tmp = a % 10;
b = b * 10 + tmp;
a = a / 10;
}
if(n > 1)
fout << -1;
else
fout << b;
fin.close();
fout.close();
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love11.07.2026
///////////////////
Bài 94. Số Palidrome là số đối xứng, nghĩa là đọc từ trái sang phải hay từ phải sang trái ta đều được 1 số. Ví dụ: 11, 121, 1331, …. Nhập 2 số nguyên dương m, n. Liệt kê dãy số vừa là số nguyên tố vừa là số Palidrome trong đoạn [m, n].
VD: input cb94.txt 100 500
Output: Kqcb94.txt 101 131 151 181 191 313 353 373 383
Gợi ý code: Cách 1:
#include <bits/stdc++.h>
using namespace std;
int palidrom(int n) {
int x = n;
int d = 0;
while (n > 0) {
d = d*10 + n%10;
n /= 10;
}
if (x == d) return 1;
else return 0;
}
int nguyenTo(int n) {
if (n < 2) return 0;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return 0;
}
return 1;
}
int main () {
freopen("cb94.txt","r",stdin);
freopen("Kqcb94.txt","w",stdout);
long m, n;
cin >> m >> n;
for (int i = m; i <= n; i++) {
if (palidrom(i) && nguyenTo(i))
cout << i << " ";
}
return 1;
}
////////////////////////////
Cách 2:
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
bool snt(long nt){
if(nt < 2) return false;
if(nt == 2 || nt == 3) return true;
if(nt % 2 == 0 || nt % 3 == 0) return false;
for(long i = 5; i * i <= nt; i += 6){
if(nt % i == 0 || nt % (i+2) == 0) return false;
}
return true;
}
bool palindrome(long pa){
long p = pa, tem = 0;
while(p > 0){
tem = tem * 10 + p % 10;
p /= 10;
}
return tem == pa;
}
int main() {
cout << "Chuong trinh tim so palidrome nguyen to trong khoang [m,n]\n";
ifstream fin("cb94.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file cb94.txt\n";
return 0;
}
long m, n;
fin >> m >> n;
fin.close();
if(m * n <= 0 || m >= n || abs(n) > 1e9) {
cerr << "so " << m << " , " << n << " khong hop le\n";
return 0;
}
cout << "Cac so vua la nguyen to vua la palindrome trong [" << m << ", " << n << "] la:\n";
for(long i = m; i <= n; i++){
if(snt(i) && palindrome(i)){
cout << i << " ";
}
}
cout << "\n";
ofstream fout("Kqcb94B.txt");
fout << "Cac so vua la nguyen to vua la palindrome trong [" << m << ", " << n << "] la:\n";
for(long i = m; i <= n; i++){
if(snt(i) && palindrome(i)){
fout << i << " ";
}
}
fout << "\n";
fout.close();
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love11.07.2026
///////////////////
Bài 95. Sử dụng hàm sort để sắp xếp tăng hay sắp xếp giảm trong mảng
Cb95.txt | Kqcb95.txt |
9 2 4 3 5 3 7 9 4 9 | 2 3 3 4 4 5 7 9 9 9 9 7 5 4 4 3 3 2 |
Bài làm
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("cb95.txt","r",stdin);
freopen("Kqcb95.txt","w",stdout);
int n;
int a[1000];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// sap xep tang:
sort(a, a + n);
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
// Sap xep giam:
sort(a, a + n, greater<int>());
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love12.07.2026
///////////////////
Bài 96. Tính tổng và tính trung bình cộng các phần tử của một dãy số. Yêu cầu đọc số phần tử n và dãy số trong file DAYSO.INP, tính toán ghi vào file DAYSO.OUT vào hai dòng: dòng thứ nhất ghi tổng, dòng thứ hai ghi giá trị trung bình cộng.
Đếm xem có bao nhiêu phần tử có giá trị lớn hơn hoặc bằng trung bình cộng của dãy số, liệt kê các phần tử này
cb96.txt | Kqcb96.txt |
6 11 21 15 17 13 19 | 96 16 21 17 19 3 16( 3 là đếm, 16 là giá trị trung bình) |
Gợi ý code:
#include <bits/stdc++.h>
using namespace std;
int n, a[1005];
int tong =0;
int main() {
freopen("cb96.txt","r",stdin);
freopen("Kqcb96.txt","w",stdout);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
tong += a[i];
}
cout << tong << endl << (float)tong / n<<"\n";
float tb = (float)tong / n;
int dem = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= tb) {
dem++;
cout << a[i] << " ";
}
}
cout << endl << dem << " " << tb;
return 0;
}
//////////////////
Bài 97. Tìm giá trị nhỏ nhất, lớn nhất của dãy số ( trong 1 vòng lặp for)
Cb97.txt | Kqcb97.txt |
10 2 4 7 9 5 7 9 4 5 6 | 2 9 |
Gợi ý code:
#include <bits/stdc++.h>
using namespace std;
int main () {
freopen("cb97.txt","r",stdin);
freopen("Kqcb97.txt","w",stdout);
int n, a[1000];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int min = a[0], max = a[0];
for (int i = 1; i < n; i++) {
if(min > a[i]) min = a[i];
if(max < a[i]) max = a[i];
}
cout <<"Gia tri nho nhat trong mang la: "<< min << endl;
cout <<"Gia tri lon nhat trong mang la: "<< max << endl ;
return 0;
}
/////////////////////////////
Bài 98. Tìm các vị trí phần tử đạt giá trị nhỏ nhất của dãy.
cb98.txt | Kqcb98.txt |
10 6 3 4 5 3 9 3 6 8 10 | 2 5 7 |
Gợi ý code:
#include <bits/stdc++.h>
using namespace std;
int main () {
freopen("cb98.txt","r",stdin);
freopen("Kqcb98.txt","w",stdout);
int n, a[1009];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int min = a[0];
for (int i = 1; i < n; i++) {
if(min > a[i]) min = a[i];
}
cout <<"Vi tri cua min= "<<min<<" trong mang la: "<< "\n";
for (int i = 0; i < n; i++) {
if (a[i] == min) cout << i + 1 << " ";
}
return 0;
}
/////////////////////////////
Bài 99. Tìm giá trị lớn thứ k của dãy số. Nhập vào số lượng phần tử n và vị trí lớn thứ k (1 dòng), dòng thứ 2 là dãy số. Yêu cầu: Ghi ra vị trí lớn thứ k trong dãy số.
cb99.txt | Kqcb99.txt |
6 3 27 13 24 19 17 20 | 20 ( 20 lớn thứ 3 trong dãy) |
Gợi ý code:
#include <bits/stdc++.h>
using namespace std;
int main(){
freopen("cb99.txt","r",stdin);
freopen("Kqcb99.txt","w",stdout);
int n, k, a[1000],b[1000];
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
memcpy(b, a, sizeof(a));
sort(b, b+n, greater<int>());
if (b[k-1] == b[0]) cout << -1;
else cout << b[k-1];
return 0;
}
Chú ý:
2 mảng tĩnh trong C/C++ không thể gán trực tiếp cho nhau bằng dấu =
Dùng vòng lặp (cách chuẩn nhất)
for(int i = 0; i < 5; i++) {
b[i] = a[i];
}
Dùng memcpy (nhanh, gọn)
memcpy(b, a, sizeof(a));
Dùng std::copy (chuẩn C++)
std::copy(a, a + 5, b);
Nhưng mảng động hoặc mảng trong std::array thì lại gán được
std::array cho phép gán:
std::array<int,5> a = {1,2,3,4,5};
std::array<int,5> b;
b = a; // ✔ Được
std::vector cũng gán được:
vector<int> a = {1,2,3,4,5};
vector<int> b;
b = a; // ✔ Được
Tóm lại
Mảng tĩnh (int a[10]) → không gán bằng = được.
Muốn copy → dùng vòng lặp, memcpy, hoặc std::copy.
Muốn gán trực tiếp → dùng std::array hoặc std::vector.
//////////////////////////////////////////////
Bài 100. Tìm dãy 3 phần tử liên tiếp có tổng lớn nhất trong một dãy số có n phần tử (n > 3). Đưa ra kết quả 3 phần tử đó và tổng của chúng.
cb100.txt | Kqcb100.txt |
8 3 4 5 8 9 2 1 1 | Tong 3 phan tu lien tiep lon nhat trong day so la: 5+8+9=22 |
Gợi ý code:
#include <bits/stdc++.h>
using namespace std;
int n, a[1006], s[1006];
int main(){
freopen("cb100.txt","r",stdin);
freopen("Kqcb100.txt","w",stdout);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n-2; i++) {
s[i] = a[i] + a[i+1] + a[i+2];
}
int m = s[0],L=0;
for (int i = 1; i < n-2; i++) {
if(m < s[i]) {m = s[i];L=i;}
}
cout <<"Tong 3 phan tu lien tiep lon nhat trong day so la: \n";
cout<<a[L]<<"+"<<a[L+1]<<"+"<<a[L+2]<<"="<<s[L];
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love12.07.2026
///////////////////
Không có nhận xét nào:
Đăng nhận xét