BzhH

P3846 [TJOI2007] 可爱的质数/【模板】BSGS ###BSGS 首先了解一下BSGS是用来干什么的,我们知道,扩展欧几里得算法可以用来解线性同余方程,那么像 at≡b(mod p)(gcd(a,p)=1)a^t\equiv b(mod~p)(gcd(a,p)=1)at≡b(mod p)(gcd(a,p)=1) 这样的方程,就是用BSGS来解决的 根据欧拉定理 ac≡ac mod ϕ(m)gcd(a,m)=1a^c\equiv a^{c~mod~\phi(m)}gcd(a,m)=1ac≡ac mod ϕ(m)gcd(a,m)=1 可以知道 ttt 是每 ϕ(p)\phi(p)ϕ(p) 次一循环,所以只需要枚举 000~phi(p)−1phi(p)-1phi(p)−1 就行了,不妨直接枚举 ppp 可以把 ppp 划分成长度为 k=p+1k=\sqrt{p}+1k=p​+1 的若干块,也可以大于这个长度,令 t=kx−y,x∈[1,k],y∈[0,k−1]t=kx-y,x\in[1,k],y\in[0,k-1]t=kx−y,x∈[1,k],y∈[0,k−1],这样就能枚举到 ...

P4884 多少个1？ 一道比较裸的BSGS题 根据题意得出 10n+10n−1+...+1≡k(mod m)⇒10n−19≡k(mod m)⇒10n≡9k+1(mod m)10^n+10^{n-1}+...+1\equiv k(mod~m)\Rightarrow \frac{10^n-1}{9}\equiv k(mod~m)\Rightarrow 10^n\equiv 9k+1(mod~m)10n+10n−1+...+1≡k(mod m)⇒910n−1​≡k(mod m)⇒10n≡9k+1(mod m) 直接套BSGS板子就行了,注意在乘的过程中可能爆long long,加个快速乘,时间复杂度 O(nlog⁡n)O(\sqrt{n}\log{n})O(n​logn) 代码 #include<iostream>#include<cstdio>#include<unordered_map>#include<cmath>using namespace std;typedef long long ll;ll ksc(ll a, ll b, ll ...

以下用 mmm 代表 max(Ai)max(A_i)max(Ai​), c(i)c(i)c(i) 表示 iii 出现的次数 法一: ∑i=1n∑j=1nlcm(Ai,Aj)=∑i=1n∑j=1nAiAjgcd(Ai,Aj)=∑d=1m1d∑i=1m∑j=1mijdc(i)c(j)[gcd(i,j)=d]=∑d=1md∑i=1md∑j=1mdijc(id)c(jd)[gcd(i,j)=1]=∑d=1md∑i=1md∑j=1mdijc(id)c(jd)∑k∣gcd(i,j)μ(k)=∑d=1m∑k=1md∑i=1mkd∑j=1mkddijc(idk)c(jdk)μ(k)k2=∑T=1mT∑k∣Tmμ(k)k(∑i=1mTic(iT))2\sum\limits_{i=1}^n\sum\limits_{j=1}^nlcm(A_i, A_j)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\frac{A_iA_j}{gcd(A_i,A_j)}\\=\sum\limits_{d=1}^m\frac{1}{d}\sum\limits_{i=1}^m\sum\limits ...

P5221 Product 这题好像可以用莫反做,但数论分块似乎会被卡 ∏i=1n∏j=1nlcm(i,j)gcd(i,j)=∏i=1n∏j=1nijgcd(i,j)2=∏i=1n∏j=1nij×∏i=1n∏j=1ngcd(i,j)−2\prod_{i=1}^n\prod_{j=1}^n\frac{lcm(i,j)}{gcd(i,j)}=\prod_{i=1}^n\prod_{j=1}^n\frac{ij}{gcd(i,j)^2}\\=\prod_{i=1}^n\prod_{j=1}^nij\times\prod_{i=1}^n\prod_{j=1}^ngcd(i,j)^{-2} i=1∏n​j=1∏n​gcd(i,j)lcm(i,j)​=i=1∏n​j=1∏n​gcd(i,j)2ij​=i=1∏n​j=1∏n​ij×i=1∏n​j=1∏n​gcd(i,j)−2 首先看 ∏i=1n∏j=1nij\prod\limits_{i=1}^n\prod\limits_{j=1}^niji=1∏n​j=1∏n​ij =∏i=1nin∏j=1nj=∏i=1ninn!=(n!)n×(n!)n=(n! ...

P3768 简单的数学题 非常典型的一道杜教筛求前缀和题目 首先我们先顺着题目给出的式子往下面推 ∑i=1n∑j=1nijgcd(i,j)=∑d=1n∑i=1n∑j=1nijd[gcd(i,j)=d]=∑d=1nd3∑i=1nd∑j=1ndij[gcd(i,j)=1]\sum\limits_{i=1}^n\sum\limits_{j=1}^nijgcd(i,j)=\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^nijd[gcd(i,j)=d]\\=\sum\limits_{d=1}^nd^3\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{n}{d}}ij[gcd(i,j)=1] i=1∑n​j=1∑n​ijgcd(i,j)=d=1∑n​i=1∑n​j=1∑n​ijd[gcd(i,j)=d]=d=1∑n​d3i=1∑dn​​j=1∑dn​​ij[gcd(i,j)=1] 用莫比乌斯反演,令 g(n)=∑i=1n∑j=1nijg(n)=\sum\limits_{i= ...

###前置知识 ####积性函数 若函数 f(n)f(n)f(n) 满足当 gcd(i,j)=1gcd(i,j)=1gcd(i,j)=1 时, f(ij)=f(i)f(j)f(ij)=f(i)f(j)f(ij)=f(i)f(j),那么这个函数为积性函数 常见的积性函数有 1.μ(n)\mu(n)μ(n) —莫比乌斯函数 2.ϕ(n)\phi(n)ϕ(n) —欧拉函数 3.d(n)d(n)d(n) —约数个数 4.σ(n)\sigma(n)σ(n) —约数和函数 ####完全积性函数 待会儿会用到 1.ϵ(n)\epsilon(n)ϵ(n) —元函数,满足 ϵ(n)=[n=1]\epsilon(n)=[n=1]ϵ(n)=[n=1] 2.I(n)I(n)I(n) —恒等函数,恒等于1 3.id(n)id(n)id(n) —单位函数,id(n)=nid(n)=nid(n)=n 可能这时你会觉得没用,当时我也是这么觉得的,但是看完下面就不会这么觉得的 ####迪利克雷卷积(*) 定义:两个数论函数 f,gf,gf,g 的卷积为 (f∗g)(n)=∑d∣nf(d)×g(nd)(f*g)(n)=\ ...

[国家集训队]Crash的数字表格 / JZPTAB 可以知道，题目中所求的是 ∑i=1n∑j=1mlcm(i,j)=∑i=1n∑j=1mijgcd(i,j)\sum\limits_{i=1}^n\sum\limits_{j=1}^mlcm(i,j)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{gcd(i,j)} i=1∑n​j=1∑m​lcm(i,j)=i=1∑n​j=1∑m​gcd(i,j)ij​ 枚举所有约数 ∑i=1n∑j=1mijgcd(i,j)=∑d=1min(n,m)∑i=1n∑j=1mijd[gcd(i,j)=d]=∑d=1min(n,m)d∑i=1⌊nd⌋∑j=1⌊md⌋ij[gcd(i,j)=1]\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{gcd(i,j)}=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{d}[gcd(i,j)=d]\\=\sum\limits ...

P3312 [SDOI2014]数表 令 g(i)g(i)g(i) 表示 iii 的所有约数和 题目要求的是 ∑i=1n∑j=1mg(gcd(i,j)),g(gcd(i,j))≤a\sum\limits_{i=1}^n\sum\limits_{j=1}^mg(gcd(i,j)),g(gcd(i,j))\le ai=1∑n​j=1∑m​g(gcd(i,j)),g(gcd(i,j))≤a 令 f(i)=∑x=1n∑y=1m[gcd(x,y)=i],F(i)=∑x=1n∑y=1m[i∣gcd(x,y)]f(i)=\sum\limits_{x=1}^n\sum\limits_{y=1}^m[gcd(x,y)=i],F(i)=\sum\limits_{x=1}^n\sum\limits_{y=1}^m[i|gcd(x,y)]f(i)=x=1∑n​y=1∑m​[gcd(x,y)=i],F(i)=x=1∑n​y=1∑m​[i∣gcd(x,y)] 那么 F(i)=∑i∣df(d)F(i)=\sum\limits_{i|d}f(d)F(i)=i∣d∑​f(d) 由莫比乌斯反演得 f(i)=∑i∣dμ(⌊ ...

P3327 [SDOI2015]约数个数和 首先可以得出 d(ij)=∑x∣i∑y∣j(gcd(x,y)=1)d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}(gcd(x,y)=1)d(ij)=x∣i∑​y∣j∑​(gcd(x,y)=1) 证明 首先令 i=p1α1p2α2...pkαk,j=p1β1p2β2...pkβki=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},j=p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}i=p1α1​​p2α2​​...pkαk​​,j=p1β1​​p2β2​​...pkβk​​ 那么 ij=p1α1+β1p2α2+β2...pkαk+βkij=p_1^{\alpha_1+\beta_1}p_2^{\alpha_2+\beta_2}...p_k^{\alpha_k+\beta_k}ij=p1α1​+β1​​p2α2​+β2​​...pkαk​+βk​​ 可以得出约数个数为 (α1+β2+1)(α2+β2+1)...(αk+βk+1)(\a ...

长期更新 主要偏向于题单,题解可能写的不会非常详细 ###CF1292B Aroma’s Search 比较明显的一道贪心题，可以看出，往前面的点走是比往后面的点走更优的，所以只需要先往前走，如果还有时间在往后走 ###CF1304C Air Conditioner 直接考虑每一个时刻能够到达的温度范围即可 ###CF1304E 1-Trees and Queries 因为题目中说了同一个点可以走多次，所以只需要考虑最短距离和 kkk 奇偶性即可 且最短距离有且只可能有三种情况 1.a→ba\rightarrow ba→b 2.a→x→y→ba\rightarrow x\rightarrow y\rightarrow ba→x→y→b 3.a→y→x→ba\rightarrow y\rightarrow x \rightarrow ba→y→x→b ###CF1322B Present 因为是异或,所以可以直接考虑每一位,判断每一位出现的 111 的次数的奇偶性 若第 iii 位为 111 那么 bi+bj∈[2k,2k+1−1]b_i+b_j\in [2^k,2^{k+1}-1]bi ...