Sundae

Sundae
10天前

Sundae
1个月前

Sundae
1个月前
5k 《你的名字》

Sundae
1个月前

Sundae
2个月前

# 唯一分解定理2

$$n = p_1^{a_1}p_2^{a_2}\cdot\cdot\cdot p_s^{a_s}$$

1. $n$有多少个正因子？
2. $n$的所有正因子和是多少？

### 因子个数

$d(n)$:表示$n$的所有正因子个数。
$$n = p_1^{a_1}p_2^{a_2}\cdot\cdot\cdot p_s^{a_s}$$

$$t = p_1^{b_1}p_2^{b_2}\cdot\cdot\cdot p_s^{b_s}$$

$$d(n) = (a_1+1)\cdot (a_2+1)\cdot\cdot\cdot(a_s+1)$$

### 因子和

$\phi(n)$:表示$n$的所有正因子之和。
$$n = p_1^{a_1}p_2^{a_2}\cdot\cdot\cdot p_s^{a_s}$$

$a_1 = 1$，

$a_1 = a_1$

$t = p_1^{a_1} * p_2^{a_2}$

$a_1 = 0$ 因子和有： $p_1^{0} * (p_2^0+p_2^1+…+p_2^{a_2})$

$a_1 = 1$因子和有：$p_1^{1} * (p_2^0+p_2^1+…+p_2^{a_2})$

$a_1 = a_1$因子和有：$p_1^{a_1} * (p_2^0+p_2^1+…+p_2^{a_2})$

$$\phi(n)=(p_1^0 + p_1^1+…+p_1^{a_1})*(p_2^0+p_2^1+…+p_2^{a_2})$$

$$\phi(n) = \frac{p_1^{a_1+1} - 1}{1 - p_1} *\frac{p_2^{a_2+1} - 1}{1 - p_2}$$

$$\phi(n) = \frac{p_1^{a_1+1} - 1}{1 - p_1}* \cdot\cdot\cdot * \frac{p_s^{a_s+1} - 1}{1 - p_s}$$

### 推广：

$n \leq 1e9$
$$\sum_{i = 1}^{n} d(i)$$

$$\sum_{i=1}^{n}\phi(i)$$

Sundae
2个月前

Sundae
2个月前
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int, vector<int >, greater<int > > heap;
for(auto x : input){
heap.push(x);
}

vector<int > res;
while(k -- ){
res.push_back(heap.top());
heap.pop();
}

return res;
}
};


Sundae
2个月前
class Solution {
public:
vector<int> maxInWindows(vector<int>& nums, int k) {
vector<int> res;
deque<int> q;
for (int i = 0; i < nums.size(); i ++ ) {
while (q.size() && q.front() <= i - k) q.pop_front();
while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();
q.push_back(i);
if (i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
};


Sundae
2个月前
#include <iostream>
#include <cmath>
using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M], g[N][M];

void init(){
for(int j = 0; j < M; ++ j){
for(int i = 1; i + (1 << j) - 1 <= n; ++ i){
if(! j){
f[i][j] = w[i];
g[i][j] = w[i];
}
else{
f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
g[i][j] = min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
}
}
}
}

int query(int l, int r){
int len = r - l + 1;
int k = log(len) / log(2);

return max(f[l][k], f[r - (1 << k)  + 1][k]) - min(g[l][k], g[r - (1 << k) + 1][k]);
}

int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i){
scanf("%d", &w[i]);
}

init();

while(m -- ){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r));
}
return 0;
}


Sundae
2个月前
#include <iostream>
#include <cmath>
using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];

void init(){
for(int j = 0; j < M; ++ j){
for(int i = 1; i + (1 << j) - 1 <= n; ++ i){
if(! j){
f[i][j] = w[i];
}
else{
f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}
}

int query(int l, int r){
int len = r - l + 1;
int k = log(len) / log(2);

return max(f[l][k], f[r - (1 << k)  + 1][k]);
}

int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++ i){
scanf("%d", &w[i]);
}

init();

scanf("%d", &m);
while(m -- ){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r));
}
return 0;
}