Cho số nguyên N, tìm số lượng x (1 < x < N) sao cho x và x+1 có cùng số ước dương. Ví dụ N=3 → 1 (vì 2 và 3 đều có 2 ước).
Tìm số ước của mọi số < N, lưu vào mảng, sau đó đếm số x thỏa mãn.
Ví dụ
#include<iostream> #include<cmath> #define N 100005 using namespace std; int table[N], pre[N]; void findPositiveDivisor() { for (int i = 1; i < N; i++) { for (int j = 1; j * j <= i; j++) { if (i % j == 0) { if (j * j == i) table[i]++; else table[i] += 2; } } } int ans = 0; for (int i = 2; i < N; i++) { if (table[i] == table[i - 1]) ans++; pre[i] = ans; } } int main() { findPositiveDivisor(); int n = 15; cout << "Number of integers: " << pre[n] << endl; }
Kết quả
Number of integers: 2