Fizzmy

数论

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章 / 数论（共12篇）

基础数论入门

（一）定理和性质一、裴蜀定理如果 a,b∈N a , b ∈ N , (a,b)=d ( a , b ) = d 那么一定存在 x,y x , y 使得 d|(a∗x+b∗y) d | ( a ∗ x + b ∗ y ) 证明：非常简单，鉴于可能有数论刚入门的OIe...

2021-08-18

0 571

Lucas定理的应用

题意：有n盏灯环形排列，顺时针依次标号为1⋯n。初始时刻为0，初始时刻第i盏灯的亮灭a[i]给定，0表示灭，1表示亮。下一时刻每盏灯的亮灭取决于当前时刻这盏灯与顺时针方向下一盏灯的亮灭。若两盏灯状态相同，则下一时刻该灯灭，否则该灯亮。求时刻t第k盏灯的状态。（n，t，k≤1e7） Soluti...

2021-08-18

0 310

bzoj1101[POI2007]Zap-莫比乌斯反演

bzoj 1101[POI2007]Zap-莫比乌斯反演题意：T组数据，每组给出m，n，d 求 ∑ni=1∑nj=1[gcd(i,j)==d](T≤50000,n,m,d<=50000) Solution: 首先大家要记住一些结论： μ∗1=[n==1] 类似地， ...

2021-08-18

0 337

BZOJ3884 上帝与集合的正确用法-扩展欧拉定理

传送门题意：求 2(2(2...))modp 的值，多组询问。 p≤107 。 Solution: 根据扩展欧拉定理，我们知道：当 b≥φ(p) 时， ab≡ab%φ(p)+φ(p)modp 此公式的具体证明可以百度扩展欧拉定理我们假设 f(p)=2(2(2...))modp ,...

2021-08-18

0 562

BZOJ2154+BZOJ2693 Crash的数字表格&jzptab-莫比乌斯反演

传送门 BZOJ2154 题意：求 ∑ni=1∑mj=1lcm(i,j) ∑ i = 1 n ∑ j = 1 m l c m ( i , j ) Solution: 看到此题首先想到这步： ∑i=1n∑j=1nlcm(i,j)=∑i=1n∑j=1nijgcd(i,j) ...

2021-08-18

0 363

BZOJ2987-earthquake

权限题。题意：给定a,b,c,求满足方程 Ax+By<=C 的非负整数解 A,B<=109,C<=min(A,B)∗109 Solution: 类欧几里得算法模板题没学过的点击这里变形一下这个式子： y<=C−AxB 但是这个式子如果直接套用...

2021-08-18

0 408

BZOJ 4596 黑暗前的幻想乡-矩阵树定理+容斥原理

传送门题意：幽香要修建幻想乡的公路。幻想乡有 N 个城市，之间原来没有任何路。幽香向选民承诺要减税，所以她打算只修 N- 1 条路将这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司，她打算让每个建筑公司都负责一条路来修。每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间...

2021-08-18

0 527

BZOJ2142 礼物-扩展lucas

传送门题意：给定n及m个数a[1…m],再给定一个模数P，求 ∑ni=1Cain−∑i−1j=1aj%P ( 1≤n≤109,1≤m≤5 ,设 P=pc11∗pc22∗pc33∗…∗pctt ， pi 为质数, 1≤pcii≤105 ) Solution: 扩展lucas定理模板...

2021-08-18

0 349

BZOJ 3930 [CQOI2015]选数-数论+递推

传送门题意：从区间[L,H]（L和H为整数）中选取N个整数，求N个整数最大公约数刚好为K的选取方案有多少个，答案模1e9+7 1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5 Solution：并不是非常理解莫反怎么做= = 注意到H-L≤10^5 尝试在这上面做文章...

2021-08-18

0 414

Codeforces 839D Winter is here-容斥

传送门题意：给出一个n个数的数列 ai a i ,考虑其中所有gcd大于1的集合，每个集合的贡献是gcd乘上集合的大小，求这个数列的总贡献%1e9+7 (1 ≤ n ≤ 200000,1 ≤ ai ≤ 1000000) ( 1 ≤ n ≤ 200000 , 1 ...

2021-08-18

0 419