Processing math: 0%

[研学] 质因数分解及素性判定

[研学] 质因数分解及素性判定

时间:2018.10 ~ 2019.3

参加成员:Modem_  Lagoon   _Qijia   mnihyc

感觉这个是人生巅峰了, Lagoon 上清华,剩下我们三也退役了,摆在这留作纪念ww  拿濑户口的话来说,就是萌新那会才是最辉煌的时期www

  • 【序言】

质数的研究一直是数学与信息学领域中的重要课题,质数的判定与质因数分解在现代通讯保密领域中更是发挥着重要的作用,本课题小组将通过此次研学机会对不同规模下自然数素性判定及质因数分解的有效算法进行探究,加深对该领域的了解和理解。

 

  • 【1.0】素数的定义

素数,又称质数。一个数 n 是素数当且仅当它是大于 1 的自然数且它的因数有且仅有 1n

 

  • 【1.1】记号与规定

    1. \displaystyle\mathbb{R} 表示实数集,\displaystyle\mathbb{N} 表示自然数集,P 表示素数集。
    2. 勒让德符号 \displaystyle\left( {\frac{n}{p}} \right)。设 \displaystyle p \in P,n \in \mathbb{N}

 

  • 【1.2】素数的一些性质

    • P 是无限集。
    • 对于任意大于 1 的自然数,它要么是个素数,要么可以分解为若干素数之积,并且在忽略顺序的情况下,这样的分解是唯一的。
    • 小于 n 的质数大约有 \ln n 个。
    • 一个合数 n 最小的素因数因数一定小于 \sqrt n
    • 费马小定理:设 p 是大于 2 的素数,则对于任意正整数 n 均有 \displaystyle \begin{array}{*{20}{c}}{{n^{p – 1}} \equiv 1}&{(\bmod p)}\end{array}
    • Mertens’ second theorem

 

  • 【2.0】素性判定

因为素数集为无限集,并且素数的分布没有规律,所以我们需要实现一个算法来判定一个数是否为素数。而素性判定算法正是这样一类算法:输入一个整数,返回这个数是“素数”还是“合数”。…

[研学] 偏序问题的研究

[研学] 偏序问题的研究

时间:2019.04 ~ 2019.09

参加成员:Modem_  Lagoon  _Qijia  mnihyc

备注:第二年就开始混水了啊(笑),只存了自己写的那部分:

  • 高维偏序

至此,k \le 3 的问题已经被我们解决了。

k = 4 呢?CDQ套CDQ?CDQ套树套树?树套树套树?

如果 k 更大,达到 k = 10 呢?十维树状数组?树套树套树套树套………?

很明显 O(n{\log ^{k – 1}}n) 的复杂度是承受不起的,需要从别的方面下手。

注意到在 k 变大的同时,n 也在变小,所以可以考虑复杂度以 n 为主的算法。

首先考虑的,当然是暴力啦)。

可以暴力枚举所有维度,并且按照这个维度(上的数)排序,这些就可以快速找出一个点控制了其它哪一些点。如果把这个信息用一个长度为 n 的二进制数表示,那么对于每个询问,只需要把它在所有维度下的二进制数取“与”运算(即能控制的点取交集),这样答案就是二进制位为 1 的数量了。

维护二进制串?当然是用 std::bitset<>  啦)。

这样复杂度就是 \displaystyle O\left( {\frac{{{n^2}k}}{{32}}} \right) ,足以通过本题了。

 

代码略。

 

这里其实还有一种在时空复杂度上的优化——分块)。

按照分块的那一套理论,把区间分成 \sqrt n 个,每块用一个 std::bitset<>  维护前缀,同时维护一个块最大值。查询的时候在块上二分,找到询问点所在的块,然后暴力加块内的点即可。时间复杂度即可缩小至 \displaystyle O\left( {\frac{{nk\sqrt n }}{{32}}} \right)

 

 …

YZOJ P4643 [BJOI2018] 链上二次求和

[BJOI2018] 链上二次求和

时间限制:4000MS     内存限制:131072KB

难度:6.2

  • 题目描述

YJC 有一棵 n 个节点的树, ii+11 \leq i < n)节点间有一条边,第 i 个点的权值为整数 a_i

现在他有 m 个询问:

操作 1(修改):给定树上两个节点 uv 和一个整数 d,表示将树上 uv 唯一的简单路径上每个点权值都加上 d

操作 2(询问):给定两个正整数 lr ,表示求树上所有节点个数大于等于 l 且小于等于 r 的简单路径节点权值和之和。由于答案很大,只用输出对质数 1000000007 取模的结果即可。

一条节点个数为 k 的简单路径节点权值和为这条上所有 k 个节点(包括端点)的权值之和,而本题中要求是对所有满足要求的简单路径,求这一权值和的和。

树边是无向的,所以路径也是无向的,即点 1 到点 2 的路径与点 2 到点 1 的路径是同一条,不要重复计算。

  • 输入格式

输入第一行包含两个正整数 nm,分别表示节点个数和操作次数。

第二行包含 n 个整数,其中第 i 个数 a_i 为第 i 个点的初始权值。

接下来 m 行,每行为 1 u v d  或 2 l r  的形式,分别表示进行一次操作 1(修改)或操作 2(询问)。

  • 输出格式

对于每次询问,输出一行一个整数,表示答案对 1000000007 取模的余数。…

[ARC092D] Two Sequences

[ARC092D] Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

难度:4.0

  • Problem Statement

You are given two integer sequences, each of length N: a_1, \cdots ,a_N and b_1, \cdots ,b_N.

There are N^2 ways to choose two integers i and j such that 1 \leq i,j \leq N. For each of these N^2 pairs, we will compute a_i+b_j and write it on a sheet of paper. That is, we will write N^2 integers in total.

Compute the XOR of these N^2 integers.

给定两个长度为 n 的正整数数组 a,b ,求 \forall 1 \leq i,j \leq na_i+b_j 在二进制下的异或和 。

  • Input

n 和两数组 a,b

  • Output

答案。

  • Sample Input

  • Sample Output

  • Constraints

\(1 \leq …

CSP-S 2019 退役游记 && 破百纪念

现在时间 UTC+8 18:18 2019/11/15,距 CSP-S 2019 还有约 14 个小时。

是时候,准备离开机房了。

(刚好也是本 blog100 篇文章,顺便纪念一下www

 …

YZOJ P4611 区间加多项式(YJC 的数组/多项式?)

YZOJ P4611 区间加多项式(YJC 的数组/多项式?)

时间限制:4444MS      内存限制:1048576KB

难度:7.2

  • 题目描述

由于本题之前被*了,所以现在数据就是随便造的,可能会因为太水又被艹     //给出题人留点面子吧qwq

YJC 在 AK 了一场校内之后,对其中的一题(P2036 「A Simple Data Structure Problem II 」)产生了兴趣。

于是他出了一题加强版(P4316 「ASDSP VII —— YJC树」),然而,他还是觉得这个加强版太简单啦!!!

所以,这次,他不仅把 K \leq 5 往后面加了三个零变成了 K \leq 5000 ,还对询问做了一点修改!

喜欢差分的 YJC 有一个长度为 N 的数组 c,初始值都为 0,下标编号为 1, 2, \cdots, N

现在 YJC 忙着 AK CSP-S2019,没空验证数据的正确性,所以只能把这个重任交给了你 —— ******,希望你能写一个程序帮他实现以下的几个操作:

opt=1,给定 L, R,输出 \sum\limits_{i=L}^R c_i 的值对 998244353 取模后的结果;

opt=0,给定 L, R 以及 K 次多项式 f(x)=\sum\limits_{k=0}^K a_kx^k,对 c_L, c_{L+1}, \cdots, c_R 分别加上 f(1), f(2), \cdots, f(R-L+1) 的值。

  • 输入格式

第一行两个正整数 N, Q ,分别表示区间范围 [1, N] 及询问数 Q

接下来,每行(除了每个 opt=0 操作的下一行)的第一个数 opt 表示操作类型。

opt=0,则接下来有两个正整数 L, R 表示操作的区间 [L, R]。紧接着下一行的第一个整数 K 表示多项式的最高次数为 K ,接下来 K+1 个整数 a_0, a_1, \cdots, a_K 分别表示多项式 f(x)= \displaystyle\sum\limits_{k=0}^K a_kx^k 的系数;

opt=1,则接下来有两个正整数 L, R 表示询问的区间 [L, R]

因为 YJC 忙着 AK CSP-S2019(之前说过了),所以他一不小心把数据给加密了。

记 …

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

时间限制:2000MS      内存限制:524288KB

难度:6.5

  • 题目描述

给定一个长度为 n 的正整数序列 \{a_i\},有 m 次操作。格式如下:

1 l r x 将区间 [l,r] 中的所有数变为 x

2 l r x 查询区间 [l,r] 中数字 x 的出现次数。

  • 输入格式

第一行两个正整数 n,m,表示序列长度和操作次数。

第二行 n 个正整数,第 i 个数为 a_i,表示序列初始值。

接下来 m 行每行四个正整数,表示操作,含义如题目所示。

  • 输出格式

对于每个询问,输出一行一个正整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 数据规模与约定

对于 20\% 的数据,\(1 \leq …

YZOJ P4621 [CSP-S 2019 四校联训 Round 1]生日悖论

YZOJ P4621 [CSP-S 2019 四校联训 Round 1]生日悖论

时间限制:1000MS      内存限制:131072KB

难度:5.0

  • 题目描述

一共有 N 种数字,所以按照包含数字的集合分类,可能有 2^N 类不同的集合。每个集合包含一种特定的数字的概率都是 \displaystyle\frac{1}{2}

随机取其中 k 个集合,请你帮忙算一下其中存在两个集合完全相同的概率。

  • 输入格式

一行两个整数 N,k

  • 输出格式

两个正整数,分别表示概率(最简分数)的分子和分母。分别对 10^6+3 取模吧。

  • 数据规模与约定

1 \leq N \leq 10^{18}2 \leq k \leq 10^{18}

 

 

Source: CodeForces 711E ZS and The Birthday Paradox

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

时间限制:4000MS      内存限制:524288KB

难度:7.0

  • 题目描述

给定一颗 n 个点的树。每个点都一个正整数点权 A_i,你需要支持以下两种操作:

1、询问点 x 和点 y 之间的路径上的所有点(包括点 x 和点 y )的点权是否构成一个从 1 开始的排列。

2、将 A_x 修改为 y

  • 输入格式

第一行一个正整数 T 表示数据组数。

接下来一行输入两个正整数 n,q 表示数的点数和询问个数。

接下来一行 n 个正整数,第 i 个正整数表示 A_i 的初值。

接下来 n-1 行每行两个正整数 u,v 表示树上的一条边 (u,v)

接下来 n 行每行三个正整数 tp,x,y 表示一个操作,其中 tp 表示操作种类。

  • 输出格式

对于每一个操作 1 如果符合条件,输出 Yes ,否则输出 No 。…

YZOJ P4587 斐波那契数列

YZOJ P4587 斐波那契数列

时间限制:1234MS      内存限制:43210KB

难度:6.5       (既然是自己搬的题还是正常一点吧w)

  • 题目描述

定义模意义下的递推数列 \displaystyle f_n=\left\{ {\begin{array}{*{20}{c}} 1&{,n \le 2}\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \end{array}} \right.,其中模数为 1000000009

给定整数 c0 \leq c < 1000000009),求出它最早出现在数列的哪个位置,并输出下标。

c 永远不会出现在此数列的任一位置,则输出 -1

  • 输入格式

多组数据。

第一行一个正整数 T0 < T \leq 100) 表示 T 组数据。

接下来 T 行每行一个数表示每组数据的 c

  • 输出格式

对于每组数据,输出一行一个数表示答案。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 5104…