头像

Sundae


访客:6405

离线:1天前


分享 数论算法

Sundae
10天前


新鲜事 原文

Sundae
1个月前
图片


新鲜事 原文

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


分享 欧拉降幂

Sundae
1个月前

daum_equation_1539185197621.png

很早写的 复杂度的分析应该是有问题。。

代码找不到了 ----
开一个map记忆化一下就好了 qaq




Sundae
2个月前

唯一分解定理2

对于任意的正整数$n$都有:
$$
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}$$

对于$n$的任何一个因子(记为:$t$)都整除$n$,而根据唯一分解定理我们可以将$t$也分解。

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

此时因为$t$是小于等于$n$的,所以$b_i \leq a_i$。则每一个$b_i$有$a_i+1$种取法。根据乘法原理:
$$
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}
$$
为了方便:设$n=p_1^{a_1} \cdot p_2^{a_2}$

对于因子:

当$a_1 = 0$,$a_2$可以选择$0, 1, 2, \cdot\cdot\cdot,a_2$

$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}$$

以此类推当$n = p_1^{a_1}p_2^{a_2}\cdot\cdot\cdot p_s^{a_s}$。

$$\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个月前
调剂太卑微了 没学校要 嘤嘤嘤


活动打卡代码 AcWing 53. 最小的k个数

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;
    }
};


活动打卡代码 AcWing 1274. 奶牛排队

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;
}


活动打卡代码 AcWing 1273. 天才的记忆

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;
}