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

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

时间:2018.10 ~ 2019.3

参加成员:Modem_  Lagoon   _Qijia   mnihyc

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

  • 【序言】

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

 

  • 【1.0】素数的定义

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

 

  • 【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】素性判定

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

YZOJ P4643 [BJOI2018] 链上二次求和

[BJOI2018] 链上二次求和

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

难度:\(6.2\)

  • 题目描述

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

现在他有 \(m\) 个询问:

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

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

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

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

  • 输入格式

输入第一行包含两个正整数 \(n\)、\(m\),分别表示节点个数和操作次数。

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

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

  • 输出格式

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

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 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 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\) 。

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

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

  • 输入格式

多组数据。

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

接下来 \(T\) 行每行一个数表示每组数据的 \(c\) 。

  • 输出格式

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

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 5104…

YZOJ P3069 字符串匹配

YZOJ P3069 字符串匹配

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

难度:\(7.0\)

  • 题目描述

给出两个串 \(A\) 和 \(B\),串中仅包含小写字母和字符 *,其中 * 能匹配任意的小写字母(也可以匹配 *)。

请你求出如果以 \(A\) 为模板串,那么有哪些 \(i\) 使得 \(B[i,i+\left|A\right|)\) 可以与  \(A\) 匹配?

  • 输入格式

第一行 \(A\),第二行 \(B\) 。

  • 输出格式

按照从小到大输出所有 \(i\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于所有数据,\(\left|A\right|, \left|B\right| \leq 500000\) 。

 

 

 …

YZOJ P2050 [FJOI2013]圆形游戏

YZOJ P2050 [FJOI2013]圆形游戏

时间限制:8000MS      内存限制:262144KB

难度:\(8.0\)

  • 题目描述

在一个无穷大的桌面上有 \(n\) 个圆形,保证任意两个圆相离或者相含,不存在相切或相交。现在 Alice 和 Bob 在玩一个圆形游戏,以 Alice 为先手,双方以如下步骤轮流游戏:

1,选定一个圆 \(A\),把 \(A\) 以及所有完全在 \(A\) 内部的圆都删除;

2,如果在自己回合无法找到可删除的圆,则输掉比赛。

假设 Alice 和 Bob 都非常聪明,请问最终谁能够取得胜利?请编程输出最终获胜的人。

  • 输入格式

输入数据的第一行为一个正整数 \(T\),表示数据组数。

接下来 \(T\) 组数据,对于每组数据,第一行包含 \(1\) 个正整数 \(n\),表示圆形的个数。

之后 \(n\) 行,每行为 \(3\) 个整数 \(x\)、\(y\) 和 \(r\) ,分别表示圆形的圆心坐标以及圆的半径。

  • 输出格式

假设 Alice 最后获胜,则输出一行 “Alice”(不包括引号),否则输出 “Bob” 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(100\%\) 的数据满足 \(T \leq 100\),\(n \leq m20000\),\(\left|x\right|, \left|y\right|, r \leq 10^8\) 。

 

 

 …

YZOJ P2966 染色

YZOJ P2966 染色

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

难度:\(7.0\)

  • 题目描述

你有 \(n\) 只猫,每一只猫认识另一些猫。但若 \(a\) 猫认识 \(b\) 猫,\(b\) 猫不一定会认识 \(a\) 猫。

现在,你需要将每一只猫染成红色或绿色。你是否可以通过染色让每一只猫都认识偶数只和自己同色的猫呢?

  • 输入格式

第一行 \(n\);

接下来 \(n\) 行,每行第一个数 \(d_i\) 表示猫 \(i\) 认识的猫的个数,后面跟着 \(d_i\) 个数表示认识的猫是哪些。

  • 输出格式

达不到要求,输出 Impossible

否则第一行输出红色猫的个数,第二行输出哪些猫是红色(那么其他猫就是绿色)

可以输出任意方案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据,\(n \leq 2000\) 。

 

 

 …

YZOJ P3451 [SDOI2013]随机数生成器问题

YZOJ P3451 [SDOI2013]随机数生成器问题

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

难度:\(6.0\)

  • 题目描述

有一个随机数生成器,可以生成 \(0\) ~ \(p-1\) 之间的伪随机整数。在生成之前,需要设定一个随机数种子 \(k\) (\(0 \leq k < p\)),则生成器第 \(1\) 次生成的整数为 \(k\)。该随机数生成器有 \(2\) 个参数 \(a, b\),如果第 \(i\) 次生成的整数为 \(x\),则第 \(i+1\) 次生成的整数为 \((ax+b) \bmod p\) 。

现给定整数 \(t\) ,我们的问题是,该随机数生成器至少需要生成多少个数,才能生成得到 \(t\)?

对于给定的 \(p,a,b,k,t\) ,请计算要使随机数生成器生成整数 \(t\),所需生成数的次数的最小值。

  • 输入格式

多组数据。第一行一个整数 \(T\) 表示数据组数,\(T \leq 50\) 。

接下来 \(T\) 行,每行五个整数 \(p,a,b,k,t\) 表示一组数据,其中 \(0 \leq a,b,k,t < p\) 。

  • 输出格式

对于每组数据,将随机数生成器的最小生成次数输出到文件中。

如果该随机数生成器无法生成整数 \(t\),输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据,\(p \leq 100\) 。

对于另外 \(30\%\) 的数据,\(a=1\) 。

对于另外 \(30\%\) 的数据,\(b=0\) 。

对于 \(100\%\) 的数据,\(p \leq 10^9\) 且 \(p\) 是质数。

 

 …

YZOJ P3056 三角形最大面积

YZOJ P3056 三角形最大面积

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

出题人:chj2001         难度:\(4.5\)

  • 题目描述

给定平面上 \(n\) 个点,定义 \(f(A,B,C)=\frac{1}{2} \left| x_A(y_B-y_C)+x_B(y_C-y_A)+x_C(y_A-y_B) \right|\) 。

每次操作都会将坐标系顺时针旋转 \(\frac{\pi}{9}\) 弧度,直到与原坐标系重合。

计算每次操作前 \(f\) 的最大值,并输出所有最大值的总和。

  • 输入格式

第一行输入一个正整数 \(n\),表示点的数量;

接下来 \(n\) 行,每行两个整数 \(x_i, y_i\) 表示最开始建立的坐标系下点的坐标。

  • 输出格式

输出所有 \(f\) 最大值的总和。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据,\(3 \leq n \leq 10000, -10000 \leq x_i, y_i \leq 10000\) 。

 

 

 …