分类 - 数论、数学

? 原创 ? ? Miller_rabin ? ? Pollard_rho ?    2021-02-28 20:41:50    1371    0    0
数论小专题——因数的分解 一、大整数质数探测 Miller_rabin算法 p" role="presentation">ppp是质数,费马小定理 ap−1=1(mod p)" role="presentation">ap−1=1(mod p)ap−1=1(mod p)a^{p-1}=1(mod\ p) p​" role="presentation">p​p​p​是质数,x2=1(mod p)→x=1 or&#xA
? 解题记录 ? ? SPOJ ? ? 亚线性筛 ?    2020-09-23 08:18:19    779    0    0
传送门 题意:计算σ0(i3)" role="presentation" style="position: relative;">σ0(i3)σ0(i3)\sigma_0(i^3)的前缀和 以前雅礼集训的时候就听说过这题,好像是洲阁筛板子? 但是如今世道不同了,Min_25" role="presentation" style="position: relative;">Min_25Min_25Min\_25筛可以把这种东西吊起来筛! 当p∈Prime,f(pc)=3c+1" role="present
? 解题记录 ? ? SPOJ ? ? 亚线性筛 ?    2020-09-23 08:18:17    543    0    0
传送门 题意:计算σ0(ik)\sigma_0(i^k)的前缀和 一道牛逼题目,Min_25Min\_25筛写的很简短。 当p∈Prime,f(pc)=ck+1p\in Prime,f(p^c)=ck+1 且当p∈Prime,f(p)=k+1p\in Prime,f(p)=k+1 又因为前缀和∑ni=1k+1=n(k+1)\sum^n_{i=1}k+1=n(k+1)可以O(1)O(1) 直接Min_25Min\_25筛就行了,复杂度O(1011)O(10^{11})能过。 #include<cstdio>#include<algorithm>#
? 解题记录 ? ? LOJ ? ? FFT|NTT ? ? 动态规划 ?    2019-03-16 07:59:01    622    0    0
传送门 题解: 考虑怎么做这道题。 首先发现性质: &#x6539;&#x53D8;&#x6B21;&#x6570;=2&#x00D7;&#x603B;&#x64CD;&#x4F5C;&#x6570;&#x2212;&#x7B54;&#x6848;&#x4E2D;&#x2032;1&#x2032;&#x7684;&#x4E2A;&#x6570;" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
? 解题记录 ? ? HDU ? ? 容斥 ? ? 莫比乌斯函数 ?    2019-03-15 15:47:54    530    0    0
GTW likes tree Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 191 Accepted Submission(s): 38 Problem Description GTW has a tree of n nodes, in which m nodes are special nodes. The value of node i is vi. Dis(x,y) is defined as
? 解题记录 ? ? BZOJ ? ? 群论 ?    2019-01-05 11:59:18    491    0    0
Description Input 输入三个整数N,M,P 1< = N <= 53 1< = M < = 1000 N< P < = 10^ 9 Output 即总数模P后的余数 Sample Input 3 2 97 Sample Output 4 论文里写的很好,觉得自己也写不出比它好的题解了qwq。 https://wenku.baidu.com/view/284648d7c1c708a1284a4425.html
? 解题记录 ? ? BZOJ ? ? 期望概率 ?    2019-01-05 11:50:47    621    0    0
Description 小Q的工作是采摘花园里的苹果。在花园中有n棵苹果树以及m条双向道路,苹果树编号依次为1到n,每条道路的两 端连接着两棵不同的苹果树。假设第i棵苹果树连接着d_i条道路。小Q将会按照以下方式去采摘苹果: 1.小Q随机移动到一棵苹果树下,移动到第i棵苹果树下的概率为d_i/(2m),但不在此采摘。 2.等概率随机选择一条与当前苹果树相连的一条道路,移动到另一棵苹果树下。 3.假设当前位于第i棵苹果树下,则他会采摘a_i个苹果,多次经过同一棵苹果树下会重复采摘。 4.重复第2和3步k次。 请写一个程序帮助计算小Q期望摘到多少苹果。 Input 第一
? 解题记录 ? ? BZOJ ? ? 高斯消元 ? ? 斯特林数 ?    2018-12-26 09:56:03    719    0    0
Description 定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与 G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中. 现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异 或为一个连通图? Input 第一行为一个整数s, 表图的个数. 接下来每一个二进制串, 第 i 行的二进制串为 gi, 其中 gi 是原图通过以下伪代码转化得 到的. 图的结点从 1 开始编号, 下面设结点数为 n.
? 解题记录 ? ? 亚线性筛 ? ? BZOJ ?    2018-12-19 20:53:45    476    0    0
Description 给定n,m,求 模10^9+7的值。 Input 仅一行,两个整数n,m。 Output 仅一行答案。 Sample Input 100000 1000000000 Sample Output 857275582 数据规模: 1&lt;=n&lt;=105&#xFF0C;1&lt;=m&lt;=109" role="presentation" style="position: relative;">1<=n<=105,1<=m<=109
? 解题记录 ? ? 杂OJ ? ? 二次剩余 ?    2018-12-19 19:15:49    364    0    0
The number x is called a square root of a modulo n (root( a, n)) if x* x = a (mod n). Write the program to find the square root of number a by given modulo n. Input One number K in the first line is an amount of tests ( K ≤ 100000). Each next line represents separate test, which contains inte