免费浏览外国网站的软件,贵州光利达建设工程有限公司局网站,wordpress排版,wordpress 超级精简文章目录莫比乌斯反演引入公式性质模板公式证明莫比乌斯函数前缀和题目练习完全平方数[HAOI2011]ProblembYY的GCD[SDOI2014]数表[国家集训队]Crash的数字表格/JZPTAB[SDOI2015]约数个数和寒假疫情期间跟着lmm学了一遍#xff0c;完全是懵逼到底状态#xff0c;以至于后面考到…
文章目录莫比乌斯反演引入公式性质模板公式证明莫比乌斯函数前缀和题目练习完全平方数[HAOI2011]ProblembYY的GCD[SDOI2014]数表[国家集训队]Crash的数字表格/JZPTAB[SDOI2015]约数个数和寒假疫情期间跟着lmm学了一遍完全是懵逼到底状态以至于后面考到或者做到相关知识的题目完全是非洲人。今天跟着h老师重新学了一遍虽然可能自己还是不会推但至少看得懂了吧
莫比乌斯反演 莫比乌斯反演形式的式子形如 F(n)∑d∣nf(d)F(n)\sum_{d|n}f(d)F(n)∑d∣nf(d)一般而言 F(n)F(n)F(n) 是非常好求的而 f(x)f(x)f(x) 即为要求的信息。
引入
F(n)∑d∣nf(d)F(n)\sum_{d|n}f(d)F(n)d∣n∑f(d) 通过这个例子可以暴力打出下列表
F(1)F(1)F(1)f(1)f(1)f(1)F(2)F(2)F(2)f(1)f(2)f(1)f(2)f(1)f(2)F(3)F(3)F(3)f(1)f(3)f(1)f(3)f(1)f(3)F(4)F(4)F(4)f(1)f(2)f(4)f(1)f(2)f(4)f(1)f(2)f(4)F(5)F(5)F(5)f(1)f(5)f(1)f(5)f(1)f(5)F(6)F(6)F(6)f(1)f(2)f(3)f(6)f(1)f(2)f(3)f(6)f(1)f(2)f(3)f(6)F(7)F(7)F(7)f(1)f(7)f(1)f(7)f(1)f(7)F(8)F(8)F(8)f(1)f(2)f(4)f(8)f(1)f(2)f(4)f(8)f(1)f(2)f(4)f(8)……
转换一下得到新表
f(1)f(1)f(1)F(1)F(1)F(1)f(2)f(2)f(2)F(2)−F(1)F(2)-F(1)F(2)−F(1)f(3)f(3)f(3)F(3)−F(1)F(3)-F(1)F(3)−F(1)f(4)f(4)f(4)F(4)−F(2)F(4)-F(2)F(4)−F(2)f(5)f(5)f(5)F(5)−F(1)F(5)-F(1)F(5)−F(1)f(6)f(6)f(6)F(6)−F(3)−F(2)F(1)F(6)-F(3)-F(2)F(1)F(6)−F(3)−F(2)F(1)f(7)f(7)f(7)F(7)−F(1)F(7)-F(1)F(7)−F(1)f(8)f(8)f(8)F(8)−F(4)F(8)-F(4)F(8)−F(4)……
看看能观察到fff与FFF之间存在什么规律 重点关注f(1),f(4),f(6),f(8)f(1),f(4),f(6),f(8)f(1),f(4),f(6),f(8) f(6)F(61)−F(62)−F(63)F(66)f(6)F(\frac{6}{1})-F(\frac{6}{2})-F(\frac{6}{3})F(\frac{6}{6})f(6)F(16)−F(26)−F(36)F(66)
发现规律 其实是知道公式了 F(nd)F(\frac{n}{d})F(dn)将ddd质因数分解p1k1...pikip_1^{k_1}...p_i^{k_i}p1k1...piki如果各质数指数均为111则该F(nd)F(\frac{n}{d})F(dn)才会存在 特别地当d1d1d1时也一定存在 f(8)F(81)−F(82)f(8)F(\frac{8}{1})-F(\frac{8}{2})f(8)F(18)−F(28) F(81)1F(\frac{8}{1})1F(18)1存在 F(82)2F(\frac{8}{2})2F(28)2质因数分解212^121存在 F(2)F(84)4F(2)F(\frac{8}{4})4F(2)F(48)4质因数分解222^222不存在 F(1)F(88)8F(1)F(\frac{8}{8})8F(1)F(88)8质因数分解232^323不存在 F(nd)F(\frac{n}{d})F(dn)前面的符号取决于ddd所含质因子的个数/种类的奇偶性(−1)k(-1)^k(−1)k f(6)F(61)−F(62)−F(63)F(66)f(6)F(\frac{6}{1})-F(\frac{6}{2})-F(\frac{6}{3})F(\frac{6}{6})f(6)F(16)−F(26)−F(36)F(66) F(61)1F(\frac{6}{1})1F(16)1不含任何质因子系数为(−1)01(-1)^01(−1)01 F(62)2F(\frac{6}{2})2F(26)2含质因子222系数为(−1)1−1(-1)^1-1(−1)1−1 F(63)3F(\frac{6}{3})3F(36)3含质因子333系数为(−1)1−1(-1)^1-1(−1)1−1 F(66)6F(\frac{6}{6})6F(66)6含质因子2,32,32,3系数为(−1)21(-1)^21(−1)21 公式
将引入中发现的规律经过数学 提炼加工打磨 规范将(−1)k(-1)^k(−1)k定义为μ(i)\mu (i)μ(i) 便成为了一个优美的 F(n)∑d∣nf(n)⇒f(n)∑d∣nμ(d)F(nd)F(n)\sum_{d|n}f(n)\Rightarrow f(n)\sum_{d|n}\mu (d)F(\frac{n}{d})F(n)d∣n∑f(n)⇒f(n)d∣n∑μ(d)F(dn) 其中μ(d)\mu(d)μ(d)为莫比乌斯函数定义如下 d1,μ(d)1d1,\mu(d)1d1,μ(d)1若ddd能改写为p1p2...pkp_1p_2...p_kp1p2...pk互异质数的积则μ(d)(−1)k\mu(d)(-1)^kμ(d)(−1)kotherwiseotherwiseotherwise其余情况μ(d)0\mu(d)0μ(d)0 性质
性质一 对于任意的正整数nnn有 ∑d∣nμ(d){1(n1)0(n≠1)\sum_{d|n}\mu(d)\left\{ \begin{aligned} 1(n1)\\ 0(n≠1) \end{aligned} \right. d∣n∑μ(d){10(n1)(n1) 证明 Ⅰ. 当n1n1n1时μ(1)1\mu(1)1μ(1)1显然成立 Ⅱ. 当n≠1n≠1n1时将nnn质因数分解为p1a1p2a2...pkaip_1^{a_1}p_2^{a_2}...p_k^{a_i}p1a1p2a2...pkai 只有所有质因子的指数都为111的因数的μ\muμ值不为000 则其中有xxx个不同质因子的个数为CkxC_k^xCkx于是有 ∑d∣nμ(d)Ck0−Ck1Ck2....∑i0k(−1)iCki\sum_{d|n}\mu(d)C_k^0-C_k^1C_k^2....\sum_{i0}^k(-1)^iC_k^id∣n∑μ(d)Ck0−Ck1Ck2....i0∑k(−1)iCki 二项式展开公式为 (XY)n∑i0nCniXiYn−i(XY)^n\sum_{i0}^nC_n^iX^iY^{n-i}(XY)ni0∑nCniXiYn−i 令X1,Y−1X1,Y-1X1,Y−1带入即可得到 ∑i0k(−1)iCki[1(−1)]k0\sum_{i0}^k(-1)^iC_k^i[1(-1)]^k0i0∑k(−1)iCki[1(−1)]k0 性质二 对于任意的正整数nnn有 ∑d∣nμ(d)dϕ(n)n\sum_{d|n}\frac{\mu(d)}{d}\frac{\phi(n)}{n}d∣n∑dμ(d)nϕ(n) 证明 ∑d∣nμ(d)dϕ(n)n⇔n×∑d∣nμ(d)dϕ(n)\sum_{d|n}\frac{\mu(d)}{d}\frac{\phi(n)}{n}\Leftrightarrow n\times \sum_{d|n}\frac{\mu(d)}{d}\phi(n)d∣n∑dμ(d)nϕ(n)⇔n×d∣n∑dμ(d)ϕ(n) 令F(n)n,f(n)ϕ(n)F(n)n,f(n)\phi(n)F(n)n,f(n)ϕ(n)则有 f(n)n×∑d∣nμ(d)d∑d∣nμ(d)nd∑d∣nμ(d)F(nd)f(n)n\times \sum_{d|n}\frac{\mu(d)}{d}\sum_{d|n}\mu(d)\frac{n}{d}\sum_{d|n}\mu(d)F(\frac{n}{d})f(n)n×d∣n∑dμ(d)d∣n∑μ(d)dnd∣n∑μ(d)F(dn) 不要忘记f(n)∑d∣nμ(d)F(nd)f(n)\sum_{d|n}\mu(d)F(\frac{n}{d})f(n)∑d∣nμ(d)F(dn)成立的前提是F(n)∑d∣nf(d)F(n)\sum_{d|n}f(d)F(n)∑d∣nf(d) 所以如果性质二要想成立就必须再证明n∑d∣nϕ(d)n\sum_{d|n}\phi(d)nd∣n∑ϕ(d) 考虑从物理意义角度出发 设k∈[1,n]gcd(n,k)d⇒gcd(n/d,k)1k∈[1,n]gcd(n,k)d\Rightarrow gcd(n/d,k)1k∈[1,n]gcd(n,k)d⇒gcd(n/d,k)1将kkk分到Cn/dC_{n/d}Cn/d类中 n8n8n8 {1,3,5,7gcd1ϕ(81)42,6gcd2ϕ(82)24gcd4ϕ(84)18gcd8ϕ(88)1\left\{ \begin{aligned} 1,3,5,7gcd1\phi(\frac{8}{1})4\\ 2,6gcd2\phi(\frac{8}{2})2\\ 4gcd4\phi(\frac{8}{4})1\\ 8gcd8\phi(\frac{8}{8})1 \end{aligned} \right.⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧1,3,5,72,648gcd1gcd2gcd4gcd8ϕ(18)4ϕ(28)2ϕ(48)1ϕ(88)1 性质三 莫比乌斯函数是一个积性函数 但我不会证明 积性函数的定义对于任意互质的整数aaa和bbb有性质f(ab)f(a)f(b)f(ab)f(a)f(b)f(ab)f(a)f(b)的数论函数 完全积性函数定义对于任意的整数aaa和bbb有f(ab)f(a)f(b)f(ab)f(a)f(b)f(ab)f(a)f(b)的数论函数 积性函数的性质 f(1)1f(1)1f(1)1积性函数的前缀和也是积性函数 模板
因为莫比乌斯函数是一个积性函数我们就可以线性筛求出其值 由此联想到我们以前会的求质数的欧拉筛法
void sieve() {mu[1] 1;for( int i 2;i n;i ) {if( ! vis[i] ) {vis[i] 1;mu[i] -1;prime[ cnt] i;}for( int j 1;j cnt i * prime[j] n;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {mu[i * prime[j]] 0; //i*prime[j]这个数至少含有prime[j]^2 break;}mu[i * prime[j]] - mu[i];//多了prime[j]这一种新的质因子 所以要与原来取相反数/*只要i*prime[j]含有pi^2早晚都会进if语句*/ }}
}公式证明
说到底好像我们似乎貌似仿佛并没有证明这个定理就直接提上裤子跑了 形式一 证明 F(n)∑d∣nf(n)⇒f(n)∑d∣nμ(d)F(nd)∑d∣nμ(d)∑k∣ndf(k)F(n)\sum_{d|n}f(n)\Rightarrow f(n)\sum_{d|n}\mu (d)F(\frac{n}{d})\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k)F(n)d∣n∑f(n)⇒f(n)d∣n∑μ(d)F(dn)d∣n∑μ(d)k∣dn∑f(k) d∣n,k∣nd⇒k∣n{d|n,k|\frac{n}{d}\Rightarrow k|n}d∣n,k∣dn⇒k∣n可以感性理解ddd取不同值kkk会把nnn所有因数都枚举到 于是可以把kkk固定下来更改ddd的取值范围类似于两层循环顺序的互调
∑k∣nf(k)∑d∣nkμ(d)\sum_{k|n}f(k)\sum_{d|\frac{n}{k}}\mu(d)k∣n∑f(k)d∣kn∑μ(d) 将性质一的结论运用上∑d∣nkμ(d)\sum_{d|\frac{n}{k}}\mu(d)∑d∣knμ(d)当且仅当nk1\frac{n}{k}1kn1时求和莫比乌斯函数值≠0≠00 f(n)f(n)f(n) 证明过程用到了性质一性质一本身其实是独立于公式的所以并不是伪证 形式二 F(n)∑n∣df(d)⇒f(n)∑n∣dμ(dn)F(d)F(n)\sum_{n|d}f(d)\Rightarrow f(n)\sum_{n|d}\mu(\frac{d}{n})F(d)F(n)n∣d∑f(d)⇒f(n)n∣d∑μ(nd)F(d) 证明 与形式一的证明大致相同 令kdnk\frac{d}{n}knd ∑k1∞μ(k)F(n×k)∑k1∞μ(k)∑n×k∣pf(p)∑n∣pf(p)∑k∣pnμ(k)\sum_{k1}^{∞}\mu(k)F(n\times k)\sum_{k1}^{∞}\mu(k)\sum_{n\times k|p}f(p)\sum_{n|p}f(p)\sum_{k|\frac{p}{n}}\mu(k)k1∑∞μ(k)F(n×k)k1∑∞μ(k)n×k∣p∑f(p)n∣p∑f(p)k∣np∑μ(k)
当且仅当pn1,pn\frac{p}{n}1,pnnp1,pn时∑k∣npμ(k)1\sum_{k|\frac{n}{p}}\mu(k)1∑k∣pnμ(k)1其余全为000 f(n)f(n)f(n) 一般这种形式更常用一些 莫比乌斯函数前缀和
基本上莫比乌斯反演的题目都会和分块绑定在一起此时的莫比乌斯函数就需要进行前缀和 接下来就让我们一起来深挖一下分块部分 Q∑i∣dμ(i)⌊ni⌋Q\sum_{i|d}\mu(i)\lfloor{\frac{n}{i}}\rfloorQi∣d∑μ(i)⌊in⌋ 不妨设n10n10n10如果按照⌊ni⌋\lfloor{\frac{n}{i}}\rfloor⌊in⌋对1≤i≤n1\le i\le n1≤i≤n进行分类 则有10{1},5{2},3{3},2{4,5},1{6,7,8,9,10}10\{1\},5\{2\},3\{3\},2\{4,5\},1\{6,7,8,9,10\}10{1},5{2},3{3},2{4,5},1{6,7,8,9,10} 反映在平面直角坐标系上看看是什么样 按照x\sqrt{x}x做分割线前半段的xxx最多只有x\sqrt{x}x段后半段的yyy最多只有x\sqrt{x}x段 拼接在一起则⌊ni⌋\lfloor{\frac{n}{i}}\rfloor⌊in⌋最多只有2n2\sqrt{n}2n个取值 n/in/in/i即为iii所在的块n/(n/i)n/(n/i)n/(n/i)则为该块右端点值
block n / i;
r n / block;因为[i,n/(n/i)][i,n/(n/i)][i,n/(n/i)]这一段的⌊ni⌋\lfloor{\frac{n}{i}}\rfloor⌊in⌋均相等 所以我们就可以对μ\muμ进行前缀和直接O(1)O(1)O(1)计算出这一段区间的sumsumsum 就不必再老实地一个一个往后推 老实人永远会被出题人吊起来抽 这个思想会在后面的题里反复出现所以提前放出来
一般情况下莫比乌斯反演后都是求 f(1)f(1)f(1) 因为这个时候 f(1)∑i1infμ(i)F(i)f(1)\sum_{i1}^{inf}\mu(i)F(i)f(1)∑i1infμ(i)F(i) 才能连续地整除分块。
infinfinf 是取决于 FFF 函数在什么时候开始就一直取值为 000后面的信息没有贡献即可停止枚举。 题目练习
完全平方数
solution
考虑二分答案转化为求[1,x][1,x][1,x]之间的无平方因子的个数 tot0tot0tot0个质数乘积的平方的倍数的数的个数111的倍数 −1-1−1个质数乘积的平方的倍数的数的个数4[22]4[2^2]4[22]的倍数9[32]9[3^2]9[32]的倍数… 222个质数乘积的平方的倍数的数的个数36[(2×3)2]36[(2\times 3)^2]36[(2×3)2]的倍数… 发现每个乘积前面的系数刚好是μ(i)\mu(i)μ(i) μ(3)−1\mu(3)-1μ(3)−1故999对答案的贡献为负μ(6)1\mu(6)1μ(6)1故363636对答案的贡献为正 xxx以内的i2i^2i2的个数为xi2\frac{x}{i^2}i2x ⇒tot(x)∑i1xμ(i)xi2\Rightarrow tot(x)\sum_{i1}^{\sqrt{x}}\mu(i)\frac{x}{i^2}⇒tot(x)i1∑xμ(i)i2x 这道题仅是莫比乌斯函数的运用并非莫比乌斯反演
code
#include cstdio
#define int long long
#define maxn 1000005
int T, k, cnt;
int mu[maxn], prime[maxn];
bool vis[maxn];void init() {mu[1] 1;for( int i 2;i maxn;i ) {if( ! vis[i] ) mu[i] -1, prime[ cnt] i;for( int j 1;j cnt i * prime[j] maxn;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {mu[i * prime[j]] 0;break;}mu[i * prime[j]] -mu[i];}}
}int check( int x ) {int ans 0;for( int i 1;i * i x;i )ans x / ( i * i ) * mu[i];return ans;
}signed main() {init();scanf( %lld, T );while( T -- ) {scanf( %lld, k );int l 1, r ( k 1 );while( l r ) {int mid ( l r ) 1;if( check( mid ) k ) r mid - 1;else l mid 1;}if( check( l ) k ) printf( %lld\n, l );else printf( %lld\n, r );}return 0;
}[HAOI2011]Problemb
solution
将a≤x≤b,c≤y≤da\le x\le b,c\le y\le da≤x≤b,c≤y≤d二维差分成四个询问 每次询问1≤x≤n,1≤y≤m1\le x\le n,1\le y\le m1≤x≤n,1≤y≤m的gcd(x,y)kgcd(x,y)kgcd(x,y)k的数对数量 然后再转化为1≤x≤nk,1≤y≤mk1\le x\le \frac{n}{k},1\le y\le \frac{m}{k}1≤x≤kn,1≤y≤km内的互质的数对数量
定义f(i):gcd(x,y)if(i):gcd(x,y)if(i):gcd(x,y)i的数对数量F(i):i∣gcd(x,y)F(i):i|gcd(x,y)F(i):i∣gcd(x,y)的数对数数量 (1≤x≤n,1≤y≤m)(1\le x\le n,1\le y\le m)(1≤x≤n,1≤y≤m)
⇒F(i)⌊ni⌋⌊mi⌋⇒f(i)∑i∣dμ(di)F(i)∑i∣dμ(di)⌊ni⌋⌊mi⌋\Rightarrow F(i)\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor\Rightarrow f(i)\sum_{i|d}\mu(\frac{d}{i})F(i)\sum_{i|d}\mu(\frac{d}{i})\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor⇒F(i)⌊in⌋⌊im⌋⇒f(i)i∣d∑μ(id)F(i)i∣d∑μ(id)⌊in⌋⌊im⌋ ⌊ni⌋⌊mi⌋\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor⌊in⌋⌊im⌋其实是一段一段的区间最多2(nm)2(\sqrt{n}\sqrt{m})2(nm)个从这里入手枚举 那么就需要对前面的∑i∣dμ(di)\sum_{i|d}\mu(\frac{d}{i})∑i∣dμ(id)前缀和
code
#include cstdio
#include iostream
using namespace std;
#define int long long
#define maxn 50005
int n, a, b, c, d, k, cnt;
bool vis[maxn];
int prime[maxn], mu[maxn], pre[maxn];void init() {mu[1] 1; for( int i 2;i maxn;i ) {if( ! vis[i] ) prime[ cnt] i, mu[i] -1;for( int j 1;j cnt i * prime[j] maxn;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {mu[i * prime[j]] 0;break;}mu[i * prime[j]] -mu[i];}}for( int i 1;i maxn;i ) pre[i] pre[i - 1] mu[i];
}int calc( int n, int m ) {if( n m ) swap( n, m );int last, ans 0;for( int i 1;i n;i last 1 ) {last min( n / ( n / i ), m / ( m / i ) );ans ( pre[last] - pre[i - 1] ) * ( n / i ) * ( m / i );}return ans;
}signed main() {init();scanf( %lld, n );for( int i 1, a, b, c, d, k;i n;i ) {scanf( %lld %lld %lld %lld %lld, a, b, c, d, k );a --, c --;a / k, b / k, c / k, d / k;printf( %lld\n, calc( b, d ) - calc( a, d ) - calc( b, c ) calc( a, c ) );}return 0;
}YY的GCD
solution
既然要求gcd(x,y)gcd(x,y)gcd(x,y)为质数而且发现这道题跟上一道problem b很像 先枚举质数剩下的不就是求1≤x≤n,1≤y≤m,gcd(n,m)11\le x\le n,1\le y\le m,gcd(n,m)11≤x≤n,1≤y≤m,gcd(n,m)1的数对数量
定义f(i):gcd(x,y)if(i):gcd(x,y)if(i):gcd(x,y)i的数对数量F(i):i∣gcd(x,y)F(i):i|gcd(x,y)F(i):i∣gcd(x,y)的数对数数量 (1≤x≤n,1≤y≤m)(1\le x\le n,1\le y\le m)(1≤x≤n,1≤y≤m) F(i)⌊ni⌋⌊mi⌋⇒f(i)∑i∣dμ(di)F(d)∑i∣dμ(di)⌊nd⌋⌊md⌋F(i)\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor\Rightarrow f(i)\sum_{i|d}\mu(\frac{d}{i})F(d)\sum_{i|d}\mu(\frac{d}{i})\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloorF(i)⌊in⌋⌊im⌋⇒f(i)i∣d∑μ(id)F(d)i∣d∑μ(id)⌊dn⌋⌊dm⌋gcd(x,y)igcd(x,y)igcd(x,y)i的质数已经提出来枚举了 ⇒ans∑pmin(n,m)f(1)∑pmin(n,m)∑d1min(n,m)μ(d)⌊nd×p⌋⌊md×p⌋\Rightarrow ans\sum_{p}^{min(n,m)}f(1)\sum_{p}^{min(n,m)}\sum_{d1}^{min(n,m)}\mu(d)\lfloor{\frac{n}{d\times p}}\rfloor\lfloor{\frac{m}{d\times p}}\rfloor⇒ansp∑min(n,m)f(1)p∑min(n,m)d1∑min(n,m)μ(d)⌊d×pn⌋⌊d×pm⌋ 如果止步于此获得的只有美丽的黑色
令kd×pkd\times pkd×p则pk/dpk/dpk/d ⇒ans∑kmin(n,m)⌊nk⌋⌊mk⌋∑p∣kμ(kp)\Rightarrow ans\sum_{k}^{min(n,m)}\lfloor{\frac{n}{k}}\rfloor\lfloor{\frac{m}{k}}\rfloor\sum_{p|k}\mu(\frac{k}{p})⇒ansk∑min(n,m)⌊kn⌋⌊km⌋p∣k∑μ(pk)
最后就只剩下对∑p∣kμ(kp)\sum_{p|k}\mu(\frac{k}{p})∑p∣kμ(pk)进行前缀和的处理 这里的处理略微不同于上一道题 可以通过暴力枚举质因子对质因子的倍数进行μ\muμ的累加再前缀和处理出来
code 遇得到哦 define int long long让我直接慢了1s多导致TTT了只能老老实实改long long才能顺利ACACAC
#include cstdio
#include iostream
using namespace std;
#define maxn 10000005
int T, cnt;
int sum[maxn], mu[maxn], prime[maxn];
long long pre[maxn];
bool vis[maxn];void init( int n ) {mu[1] 1;for( int i 2;i n;i ) {if( ! vis[i] ) prime[ cnt] i, mu[i] -1;for( int j 1;j cnt i * prime[j] maxn;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {mu[i * prime[j]] 0;break;}mu[i * prime[j]] -mu[i];}}for( int j 1;j cnt;j )for( int i 1;i * prime[j] n;i )sum[prime[j] * i] mu[i];for( int i 1;i maxn;i ) pre[i] pre[i - 1] sum[i];
}int main() {init( 1e7 );scanf( %d, T );int n, m, r;long long ans;while( T -- ) {scanf( %d %d, n, m );if( n m ) swap( n, m );ans 0;for( int i 1;i n;i r 1 ) {r min( n / ( n / i ), m / ( m / i ) );ans 1ll * ( pre[r] - pre[i - 1] ) * ( n / i ) * ( m / i );}printf( %lld\n, ans );}return 0;
}[SDOI2014]数表
solution
一句话题意令sum(i)sum(i)sum(i)表示iii的因子和给定n,m,an,m,an,m,a求 ∑1≤i≤n,1≤j≤msum(gcd(i,j))≤asum(gcd(i,j))\sum_{1\le i\le n,1\le j\le m}^{sum(gcd(i,j))\le a}sum(gcd(i,j))1≤i≤n,1≤j≤m∑sum(gcd(i,j))≤asum(gcd(i,j))
先思考此题的弱化版即不考虑aaa ∑i1n∑j1msum(gcd(i,j))\sum_{i1}^n\sum_{j1}^msum(gcd(i,j))i1∑nj1∑msum(gcd(i,j)) 令F(i)F(i)F(i)表示1≤x≤n,1≤y≤m,i∣gcd(x,y)1\le x\le n, 1\le y\le m,i|gcd(x,y)1≤x≤n,1≤y≤m,i∣gcd(x,y)的数对个数 令f(i)f(i)f(i)表示1≤x≤n,1≤y≤m,gcd(x,y)i1\le x\le n,1\le y\le m,gcd(x,y)i1≤x≤n,1≤y≤m,gcd(x,y)i的数对个数 则有 F(i)∑i∣df(d),F(i)⌊ni⌋⌊mi⌋F(i)\sum_{i|d}f(d),F(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloorF(i)i∣d∑f(d),F(i)⌊in⌋⌊im⌋ 莫比乌斯反演 f(i)∑i∣dμ(di)F(d)∑i∣dμ(di)⌊nd⌋⌊md⌋f(i)\sum_{i|d}\mu(\frac{d}{i})F(d)\sum_{i|d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloorf(i)i∣d∑μ(id)F(d)i∣d∑μ(id)⌊dn⌋⌊dm⌋ 于是有 ans∑i1min(n,m)sum(i)f(i)ans\sum_{i1}^{min(n,m)}sum(i)f(i)ansi1∑min(n,m)sum(i)f(i)∑i1min(n,m)sum(i)∑i∣dμ(di)⌊nd⌋⌊md⌋\sum_{i1}^{min(n,m)}sum(i)\sum_{i|d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloori1∑min(n,m)sum(i)i∣d∑μ(id)⌊dn⌋⌊dm⌋∑d1min(n,m)⌊nd⌋⌊md⌋∑i∣dsum(i)μ(di)\sum_{d1}^{min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{i|d}sum(i)\mu(\frac{d}{i})d1∑min(n,m)⌊dn⌋⌊dm⌋i∣d∑sum(i)μ(id) 如果现在知道∑i∣dsum(i)μ(di)\sum_{i|d}sum(i)\mu(\frac{d}{i})∑i∣dsum(i)μ(id)就可以O(sqrtn)O(sqrt{n})O(sqrtn)的计算出答案 sum(i)sum(i)sum(i)可以线性筛得到与上一题类似枚举iii暴力更新倍数前缀和即可O(logn)O(logn)O(logn)
现在加上限制aaa又怎么做呢 其实只有sum(i)≤asum(i)\le asum(i)≤a的iii才会产生贡献 自然而然的想到将a,sum(i)a,sum(i)a,sum(i)分别排序树状数组维护 本质就是树状数组在线插入
至于取模的问题采取自然溢出的方式即可具体细节可参见代码
code
#include cstdio
#include iostream
#include algorithm
using namespace std;
#define maxn 100000
#define int long long
struct node {int n, m, a, id;
}q[maxn], s[maxn];
int prime[maxn], mu[maxn 5], sum[maxn 5], tree[maxn 5], result[maxn 5];
bool vis[maxn 5];
int cnt;bool cmp( node x, node y ) {return x.a y.a;
}void init() {mu[1] 1;for( int i 2;i maxn;i ) {if( ! vis[i] ) prime[ cnt] i, mu[i] -1;for( int j 1;j cnt i * prime[j] maxn;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {mu[i * prime[j]] 0;break;}mu[i * prime[j]] -mu[i];}}for( int i 1;i maxn;i )for( int j i;j maxn;j i ) sum[j] i;for( int i 1;i maxn;i )s[i].a sum[i], s[i].id i;sort( s 1, s maxn 1, cmp );
}int lowbit( int x ) {return x ( -x );
}void add( int x, int v ) {for( int i x;i maxn;i lowbit( i ) )tree[i] v;
}int query( int x ) {int ans 0;for( int i x;i;i - lowbit( i ) )ans tree[i];return ans;
}int solve( int n, int m ) {if( n m ) swap( n, m );int ans 0, r;for( int i 1;i n;i r 1 ) {r min( n / ( n / i ), m / ( m / i ) );ans ( n / i ) * ( m / i ) * ( query( r ) - query( i - 1 ) );}return ans;
}void Add( int id ) {for( int i 1;i * id maxn;i )add( i * id, mu[i] * sum[id] );
}signed main() {int Q;scanf( %lld, Q );for( int i 1;i Q;i )scanf( %lld %lld %lld, q[i].n, q[i].m, q[i].a ), q[i].id i;sort( q 1, q Q 1, cmp );init();int now 0;for( int i 1;i Q;i ) {while( s[now 1].a q[i].a now maxn ) Add( s[ now].id );result[q[i].id] solve( q[i].n, q[i].m );}int mod 1ll 31;for( int i 1;i Q;i )printf( %lld\n, result[i] % mod );return 0;
}[国家集训队]Crash的数字表格/JZPTAB
solution 一句话题意求∑i1n∑j1mlcm(i,j)\sum_{i1}^n\sum_{j1}^mlcm(i,j)i1∑nj1∑mlcm(i,j)step1:step1:step1: 枚举最大公因数
∑d1min(n,m)∑i1n∑j1mi×jd\sum_{d1}^{min(n,m)}\sum_{i1}^n\sum_{j1}^m\frac{i\times j}{d}d1∑min(n,m)i1∑nj1∑mdi×j
step2:step2:step2: 将最大公因数提到前面循环上界压缩
∑d1min(n,m)∑i1⌊nd⌋∑j1⌊md⌋i×d×j×dd∑d1min(n,m)d∑i1⌊nd⌋∑j1⌊md⌋i×j[gcd(i,j)1]\sum_{d1}^{min(n,m)}\sum_{i1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j1}^{\lfloor\frac{m}{d}\rfloor}\frac{i\times d\times j\times d}{d}\sum_{d1}^{min(n,m)}d\sum_{i1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j1}^{\lfloor\frac{m}{d}\rfloor}i\times j\ \ \ \ \ \ \ \ \ \ [gcd(i,j)1]d1∑min(n,m)i1∑⌊dn⌋j1∑⌊dm⌋di×d×j×dd1∑min(n,m)di1∑⌊dn⌋j1∑⌊dm⌋i×j [gcd(i,j)1]
step3:step3:step3: 利用∑i∣nμ(i)[n1]\sum_{i|n}\mu(i)[n1]∑i∣nμ(i)[n1]对原式不会造成改变
∑d1min(n,m)d∑i1⌊nd⌋∑j1⌊md⌋∑k∣gcd(i,j)μ(k)×i×j\sum_{d1}^{min(n,m)}d\sum_{i1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j1}^{\lfloor\frac{m}{d}\rfloor}\sum_{k|gcd(i,j)}\mu(k)\times i\times jd1∑min(n,m)di1∑⌊dn⌋j1∑⌊dm⌋k∣gcd(i,j)∑μ(k)×i×j
step4:step4:step4: 也将μ\muμ提到前面那么为了保证k∣i,k∣jk|i,k|jk∣i,k∣j枚举i,ji,ji,j变为直接枚举ki,kjki,kjki,kj
∑d1min(n,m)d∑kmin(⌊nd⌋,⌊md⌋)∑ki⌊nd⌋∑kj⌊md⌋μ(k)×k2×i×j\sum_{d1}^{min(n,m)}d\sum_{k}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\sum_{ki}^{\lfloor\frac{n}{d}\rfloor}\sum_{kj}^{\lfloor\frac{m}{d}\rfloor}\mu(k)\times k^2\times i\times jd1∑min(n,m)dk∑min(⌊dn⌋,⌊dm⌋)ki∑⌊dn⌋kj∑⌊dm⌋μ(k)×k2×i×j
step5:step5:step5: 将kkk提出来
∑d1min(n,m)d∑kmin(⌊nd⌋,⌊md⌋)μ(k)×k2∑i1⌊nd×k⌋∑j1⌊md×k⌋i×j\sum_{d1}^{min(n,m)}d\sum_{k}^{min(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(k)\times k^2\sum_{i1}^{\lfloor\frac{n}{d\times k}\rfloor}\sum_{j1}^{\lfloor\frac{m}{d\times k}\rfloor}i\times jd1∑min(n,m)dk∑min(⌊dn⌋,⌊dm⌋)μ(k)×k2i1∑⌊d×kn⌋j1∑⌊d×km⌋i×j
⚡ ①∑kmin(⌊nd⌋,⌊md⌋)μ(k)×k2\sum_{k}^{min(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(k)\times k^2∑kmin(⌊dn⌋,⌊dm⌋)μ(k)×k2使用老套路前缀和优化之后O(1)O(1)O(1)查询 ②∑i1⌊nd×k⌋∑j1⌊md×k⌋i×j\sum_{i1}^{\lfloor\frac{n}{d\times k}\rfloor}\sum_{j1}^{\lfloor\frac{m}{d\times k}\rfloor}i\times j∑i1⌊d×kn⌋∑j1⌊d×km⌋i×j其实就是一个等差数列求积 ∑i1n∑j1mi×jn×(n1)2.m×(m1)2\sum_{i1}^n\sum_{j1}^mi\times j\frac{n\times (n1)}{2}. \frac{m\times (m1)}{2}i1∑nj1∑mi×j2n×(n1).2m×(m1) code
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 20101009
#define maxn 10000005
int mu[maxn], prime[maxn], sum[maxn];
bool vis[maxn];
int cnt, inv;void init() {mu[1] 1;for( int i 2;i maxn;i ) {if( ! vis[i] ) prime[ cnt] i, mu[i] -1;for( int j 1;j cnt i * prime[j] maxn;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {mu[i * prime[j]] 0;break;}mu[i * prime[j]] -mu[i];}}for( int i 1;i maxn;i )sum[i] ( sum[i - 1] i % mod * i % mod * mu[i] % mod mod ) % mod;
}int seq( int n ) {return n % mod * ( n 1 ) % mod * inv % mod;
}int calc( int n, int m ) {if( n m ) swap( n, m );int ans 0, r;for( int i 1;i n;i r 1 ) {r min( n / ( n / i ), m / ( m / i ) );ans ( ans ( sum[r] - sum[i - 1] mod ) % mod * seq( n / i ) % mod * seq( m / i ) % mod ) % mod;}return ans;
}int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}signed main() {init();inv qkpow( 2, mod - 2 );int n, m;scanf( %lld %lld, n, m );int ans 0;for( int d 1;d min( n, m );d )ans ( ans d * calc( n / d, m / d ) % mod ) % mod;printf( %lld\n, ans );return 0;
} [SDOI2015]约数个数和
solution 一句话题意设d(x)d(x)d(x)表示xxx的约数和求
∑i1n∑j1md(i×j)\sum_{i1}^n\sum_{j1}^md(i\times j)i1∑nj1∑md(i×j) 首先有一个约数和的公式 我不是很会证 d(i×j)∑x∣i∑y∣j[gcd(x,y)1]d(i\times j)\sum_{x|i}\sum_{y|j}[gcd(x,y)1]d(i×j)x∣i∑y∣j∑[gcd(x,y)1] ∑i1n∑j1m∑x∣i∑y∣j[gcd(x,y)1]\sum_{i1}^n\sum_{j1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)1]i1∑nj1∑mx∣i∑y∣j∑[gcd(x,y)1] 转换一下枚举方式考虑直接枚举因子 ∑i1n∑j1m⌊ni⌋⌊mj⌋(gcd(i,j)1)\sum_{i1}^n\sum_{j1}^m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\ \ (gcd(i,j)1)i1∑nj1∑m⌊in⌋⌊jm⌋ (gcd(i,j)1) 设F(i)F(i)F(i)表示1≤x≤n,1≤y≤m,i∣gcd(x,y)1\le x\le n,1\le y\le m,i|gcd(x,y)1≤x≤n,1≤y≤m,i∣gcd(x,y)的约数和 设f(i)f(i)f(i)表示1≤x≤n,1≤y≤m,igcd(x,y)1\le x\le n,1\le y\le m,igcd(x,y)1≤x≤n,1≤y≤m,igcd(x,y)的约数和f(1)f(1)f(1)即为最终答案 F(p)∑p∣df(d),F(p)∑i1⌊np⌋∑j1⌊mp⌋⌊ni∗p⌋⌊mj∗p⌋F(p)\sum_{p|d}f(d),F(p)\sum_{i1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j1}^{\lfloor\frac{m}{p}\rfloor}\lfloor\frac{n}{i*p}\rfloor\lfloor\frac{m}{j*p}\rfloorF(p)p∣d∑f(d),F(p)i1∑⌊pn⌋j1∑⌊pm⌋⌊i∗pn⌋⌊j∗pm⌋ 莫比乌斯反演 f(p)∑p∣tμ(tp)F(t)∑p∣tμ(tp)∑i1⌊nt⌋∑j1⌊mt⌋⌊ni∗t⌋⌊mj∗t⌋f(p)\sum_{p|t}\mu(\frac{t}{p})F(t)\sum_{p|t}\mu(\frac{t}{p})\sum_{i1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j1}^{\lfloor\frac{m}{t}\rfloor}\lfloor\frac{n}{i*t}\rfloor\lfloor\frac{m}{j*t}\rfloorf(p)p∣t∑μ(pt)F(t)p∣t∑μ(pt)i1∑⌊tn⌋j1∑⌊tm⌋⌊i∗tn⌋⌊j∗tm⌋ 最后想求的答案就是f(1)f(1)f(1) ∑t1min(n,m)μ(t)F(t),F(t)∑i1⌊nt⌋∑j1⌊mt⌋⌊nit⌋⌊mjt⌋\sum_{t1}^{min(n,m)}\mu(t)F(t),F(t)\sum_{i1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j1}^{\lfloor\frac{m}{t}\rfloor}\lfloor\frac{n}{it}\rfloor\lfloor\frac{m}{jt}\rfloort1∑min(n,m)μ(t)F(t),F(t)i1∑⌊tn⌋j1∑⌊tm⌋⌊itn⌋⌊jtm⌋
对于求F(t)F(t)F(t)的方法先计算出S(t)∑i1t⌊ti⌋S(t)\sum_{i1}^t\lfloor\frac{t}{i}\rfloorS(t)∑i1t⌊it⌋则可以O(1)O(1)O(1)得到
code
#include cstdio
#include iostream
using namespace std;
#define int long long
#define maxn 50005
int T, n, m, cnt;
int mu[maxn], prime[maxn], sum[maxn];
bool vis[maxn];void init() {mu[1] 1;for( int i 2;i maxn;i ) {if( ! vis[i] ) prime[ cnt] i, mu[i] -1;for( int j 1;j cnt i * prime[j] maxn;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {mu[i * prime[j]] 0;break;}mu[i * prime[j]] -mu[i];}}for( int i 1;i maxn;i ) mu[i] mu[i - 1];for( int x 1;x maxn;x ) {int ans 0;for( int i 1, j;i x;i j 1 ) {j x / ( x / i );ans ( j - i 1 ) * ( x / i );}sum[x] ans;}
}int calc( int n, int m ) {if( n m ) swap( n, m );int ans 0, r;for( int i 1;i n;i r 1 ) {r min( n / ( n / i ), m / ( m / i ) );ans ( mu[r] - mu[i - 1] ) * sum[n / i] * sum[m / i];}return ans;
}signed main() {init();scanf( %lld, T );while( T -- ) {scanf( %lld %lld, n, m );printf( %lld\n, calc( n, m ) );}return 0;
}
