3
1
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
46
45
Giải thích thuật toán:
Ở đây sử dụng thuật toán sàng số nguyên tố, chi tiết bạn có thể tìm hiểu. Nhưng đại khái là cho n chia i (i chạy từ 2 đến vô cùng) cho đến khi n còn cái nịt. Lúc đầu, i = 2, n chia i đến khi không chia được nữa, không chia được 2 thì nghiễm nhiên không chia được 4,6,8,... Khi n không còn khả năng chia được 2, i tăng giá trị cho đến khi n chia được i, giả sử là 3, tương tự... nghiễm nhiên không chia được 6,9,12,...
Lúc này ta lưu số lần chia được cho các số nguyên tố (2,3,5,7,...) vào mảng riêng với giá trị tương ứng, chia được 1 lần cộng 1 lần, tức số mũ +1. Lục lại mảng này ta được kết quả.
Ví dụ: 420 = 2^2*3*5*7. Số mũ lần lượt là 2 1 1 1
F[0] = 0
F[1] = 0
F[2] = 2
F[3] = 1
F[4] = 0
F[5] = 1
F[6] = 0
F[7] = 1
Chương trình C++:
#include <bits/stdc++.h>
#define N 1000000
#define ll long long
using namespace std;
ll f[N+2], n, s, p;
int main()
{
freopen("SumExpo.INP","r",stdin);
freopen("SumExpo.OUT","w",stdout);
cin >> n;
int i=2;
while (n>1)
{
if (n % i == 0)
{
while (n % i == 0)
{
f[i]++;
n = n/i;
}
}
i++;
}
for (int i=1; i<=1000000; i++)
if (f[i] > 0)
{
if (f[i]%2 == 0)
s = s+f[i];
if (f[i]%2 == 1)
p = p+f[i];
}
cout << s << endl << p;
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
0. Gọi 5 là tổng các số mũ X, có giá trị chẵn và P là tổng các số mũ X, có giá ...
Bảng tin