P2522 [HAOI2011]Problem b 题意： n个询问，在 a ≤ x ≤ b , c ≤ y ≤ d a\le x\le b, c \le y \le d a≤x≤b,c≤y≤d范围内，满足gcd(x,y)=k的数对有多少个。 Solution: 反演过程 法一：  ∑ x = a b ∑ y = c d [ g c d ( x , y ) = k ] = ∑ x = a b ∑ y = c d ∑ k ∣ g c d ( x , y ) [ g c d ( x k , y k ) = 1 ] = ∑ x = ⌈ a k ⌉ ⌊ b k ⌋ ∑ y = ⌈ c k ⌉ ⌊ d ...

P1390 公约数的和 题意： 给定n，求  ∑ i = 1 n ∑ j = i + 1 n g c d ( i , j ) \sum_{i=1}^{n}\sum_{j=i+1}^{n}gcd(i,j) i=1∑n​j=i+1∑n​gcd(i,j) 其中gcd(i,j)表示i和j的最大公约数。 Solution： 法一：  ∑ i = 1 n ∑ j = i + 1 n g c d ( i , j ) = ∑ d = 1 n d ∑ i = 1 n ∑ j = i + 1 n [ g c d ( i , j ) = d ] = ∑ d = 1 n d ∑ i = 1 n ∑ j = 1 n [...

P3811 【模板】乘法逆元 O（n）求1~n的逆元 #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,p; int inv[3000005]; int main() {  scanf("%d%d",&n,&p); inv[1]=1; printf("1\n"); for(int i=2;i<=n;i++) {  inv[i]=1ll*(p-p/i)*inv[p%i]%p; printf("%d\n",in...

P5431 【模板】乘法逆元2 题意：  Solution： 这题主要是学一个想法。  s i = a 1 ∗ a 2 ∗ . . . ∗ a i 1 s i = 1 a 1 ∗ a 2 ∗ . . . ∗ a i 1 s i − 1 = 1 s i ∗ a i 1 a i = s i − 1 s i s_i=a_1*a_2*...*a_i \\ \frac{1}{s_i}=\frac{1}{a_1*a_2*...*a_i} \\ \frac{1}{s_{i-1}}=\frac{1}{s_i}*a_i \\ \frac{1}{a_i}=\frac{s_{i-1}}{s_i} si​=a1​∗a...

小x的奇遇-adventure 题意： 给定函数f(n),g(n),求 G k ( n ) G_k(n) Gk​(n)  f ( n ) = { 1 , n = 1 ∑ i = 1 n − 1 [ g c d ( i , n − i ) = = 1 ] , n > 1 f(n)=\begin{cases} 1,n=1\\ \sum_{i=1}^{n-1}[gcd(i,n-i)==1],n>1 \end{cases} f(n)={ 1,n=1∑i=1n−1​[gcd(i,n−i)==1],n>1​  g ( n ) = ∑ d ∣ n f ( n d ) g(n)=\sum_{...

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_{a_1=L}^H\sum_{a_2=L}^H...\sum_{a_n=L}^H[gcd(a_1,a_2,...,a_n)=k] a1​=L∑H​a2​=L∑H​...an​=L∑H​[gcd(a1​,a2​,...,an​)=k] Solution  ∑ a 1 = L H ∑ a 2 = L H ....

简单题 题意： 求：  ∑ 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∑n​j=1∑m​gcd(i,j)φ(ij)μ(ij) 多组数据。 为了减小输出大小，你只需输出上式模 2 32 2^{32} 232的值 Solution： 首先知道一些函数的特点:  φ ( i j ) = φ ( i ) φ ( j ) g c d ( i , j ) φ ( g c d ( i , j ) ) μ ( i j ) = μ ( i ...

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∑n​j=1∑m​d(ij) Solution: 首先需知道一个推导结果：  d ( i j ) = ∑ x ∣ i ∑ y ∣ j [ g c d ( x , y ) = 1 ] d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1] d(ij)=x∣i∑​y∣j∑​[gcd(x,y)=1] 然后开始式子的推导：  ∑ i...

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)) ans(n)=∑i=1n​∑j=1n​φ(ij)φ(gcd(i,j)) Solution:  a n s ( n ) = ∑ i = 1 n ∑ j = 1 n φ ( i j ) φ ( g c d ( i , j ) ) = ∑ i = 1 n ∑ j = 1 n φ ( i ) φ ( j ) g...

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 , . . . , a x ) ) ∗ g c d ( a 1 , a 2 , . . . , a x ) \sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})f(gcd(a_1,a_2,...,a_x))*gc...

当点的顺序被打乱： 时间复杂度： O ( N ) O(N) O(N) 空间复杂度： O ( N ) O(N) O(N) 否则，时间复杂度可能为 O ( N 3 ) O(N^3) O(N3) #include<bits/stdc++.h> using namespace std; const int N=5e3+10; const double eps=1e-12; double R; int n; struct node {  double x,y; }point[N],O; double getDistance(node p)//与圆心之间的距离 {  return sqrt((...

Contest - 2021-03-10 个人排位赛1 A-Marathon III B-Piggy Back C-Cow Jog III D-Learning by Example E-Crosswords F-Marathon I G-Marathon II H-Cow Jog I I-Guard Mark J-Cow Jog II Contest - 2021-03-11 个人排位赛2 A-Cow Routing I B-Stampede C-Cow Routing II D-Meeting Time II E-Cow Routing III F-Meeting Time I G-Moo...

Sjekira 题意： 给了你n个点权，n-1条边（题目保证这个图是棵树），问你将这n-1条边都砍掉的花费和最小是多少。 砍掉一条边的花费是这条边所连的两个联通块最大的点权之和。 Solution： 因为要使最后砍完n-1条边之后的花费最小，可以贪心的知道，每次都是先将点权最大的点所连的边先砍掉，这样能够保证点权大的点被用到的次数尽可能的少。因此每次都先砍掉点权最大的点所连的边，然后对这条边的另一个联通块（即与点权最大的点所连的边的另外一个联通块）求一下点权最大，每次都重复这样的操作（删除的边不用再重复删除）。但是这样写的话，可能比较复杂，因此我们反着进行思考，将点权从小到大排序，依次加入该点...

Needle 题意： 有三条栅栏，相邻之间的栅栏距离为1 unit，每条栅栏上都有若干个点（点的横坐标已知），问有多少中穿过栅栏的方案。 Solution： 记第一个栅栏上的点为a[i],第二个为b[j]，第三个为c[k] 根据几何的性质（相似性质）可知，若一个针能穿过三个栅栏，那么a[i]+c[k]=2*b[j]，若是暴力枚举，肯定会Tle，所以我们要将其转换为多项式的乘法，利用FFT去求解。  ∑ i = 1 n u ∑ j = 1 n m ∑ k = 1 n l [ a [ i ] + c [ k ] = 2 ∗ b [ j ] ] = ∑ i = 1 n u ∑ j = 1 n m ∑...