zjnu_tjq

题解

未归档(3) 板子(2)

/ 注册

全部文章 / 题解（共104篇）

P3172 [CQOI2015]选数（莫比乌斯反演+杜教筛）

P3172 [CQOI2015]选数题意给定区间[L,H]，区间内n个数的最大公约数为k的方案书有多少个。即求 ∑ a 1 = L H ∑ a 2 = L H . . . ∑ a n = L H [ g c d ( a 1 , a 2 , . . . , a n ) = k ] \sum_...

2021-08-14

0 368

简单题（莫比乌斯反演+公式）

简单题题意：求： ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) φ ( i j ) μ ( i j ) \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)\varphi(ij)\mu(ij) i=1∑nj=1∑mgcd(i,j)φ(ij)μ(ij...

2021-08-14

0 436

P3327 [SDOI2015]约数个数和 (莫比乌斯反演+公式)

P3327 [SDOI2015]约数个数和题意：设d(x)为x的约数个数，给定 n , m n,m n,m，求 ∑ i = 1 n ∑ j = 1 m d ( i j ) \sum_{i=1}^{n}\sum_{j=1}^{m}d(ij) i=1∑nj=1∑md(ij) Soluti...

2021-08-14

0 472

phi and phi（莫比乌斯反演+公式）

phi and phi 题意：求 a n s ( n ) = ∑ i = 1 n ∑ j = 1 n φ ( i j ) φ ( g c d ( i , j ) ) ans(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(ij)\varphi(gcd(i,j)) ...

2021-08-14

0 402

A Very Easy Math Problem（莫比乌斯反演）

A Very Easy Math Problem 题意：给定 n , x , k n,x,k n,x,k，求解： ∑ a 1 = 1 n ∑ a 2 = 1 n . . . ∑ a x = 1 n ( ∏ j = 1 x a j k ) f ( g c d ( a 1 , a 2 , . ....

2021-08-14

0 321

Sjekira（逆向思维+带权并查集）

Sjekira 题意：给了你n个点权，n-1条边（题目保证这个图是棵树），问你将这n-1条边都砍掉的花费和最小是多少。砍掉一条边的花费是这条边所连的两个联通块最大的点权之和。 Solution：因为要使最后砍完n-1条边之后的花费最小，可以贪心的知道，每次都是先将点权最大的点所连的边先...

2021-08-14

0 430

Needle(FFT)

Needle 题意：有三条栅栏，相邻之间的栅栏距离为1 unit，每条栅栏上都有若干个点（点的横坐标已知），问有多少中穿过栅栏的方案。 Solution：记第一个栅栏上的点为a[i],第二个为b[j]，第三个为c[k] 根据几何的性质（相似性质）可知，若一个针能穿过三个栅栏，那么a[i]...

2021-08-14

0 544

Euklid

Euklid 题意：定义一个函数如下： R ( a , b ) = { R ( b , a ) i f a < b R ( ⌊ a b ⌋ , b ) i f a > = b > 1 a i f a > = b = 1 R(a,b)=\begin{case...

2021-08-14

0 434

牛客小白月赛36

牛客小白月赛36 A 好哥哥题意给定一段合法括号序列和元钱，合法括号序列的定义如下：1.是合法的括号序列。2.若字符串是合法的括号序列，那么(A)也是合法的括号序列。3.若字符串A,B是合法的括号序列，那么AB也是合法的括号序列。我们设定表示第对括号的层数，即：它前面有多少未匹配的左括号。同时规...

2021-08-14

0 520

杜教筛(推导方法)

杜教筛求积性函数的前缀和 O ( n 3 4 ) O(n^{\frac{3}{4}}) O(n43)，预处理后的时间复杂度 O ( n 2 3 ) O(n^{\frac{2}{3}}) O(n32) 一般的推导过程 ( f ∗ g ) ( n ) = g ( d ) f ( n d ) (...

2021-08-14

0 392