数论小专题——因数的分解
一、大整数质数探测 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">ppp是质数，x2=1(mod p)→x=1 or

传送门
题意：计算σ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
传送门
题意：计算σ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>#
传送门
题解：
考虑怎么做这道题。
首先发现性质：
改变次数=2×总操作数−答案中′1′的个数" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
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
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
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
第一
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.
Description
给定n,m，求 模10^9+7的值。
Input
仅一行，两个整数n,m。
Output
仅一行答案。
Sample Input
100000 1000000000
Sample Output
857275582
数据规模：
1<=n<=105，1<=m<=109" role="presentation" style="position: relative;">1<=n<=105，1<=m<=109
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
Rockdu's Blog