题意 求$gcd(i, j)$为素数的对数，$ i \leqslant N ,j \leqslant N$ Sol 一开以为要用zap那题的思路暴力求，但是化到一半发现会做了qwq。 设$p_i$为第$i$个素数 我们要求的是 $$ans = \sum_{i = 1}^n \sum_{j = 1}^n [gcd(i, j) = p_i]$$ $$ = \sum_{i = 1}^{\frac{n}{...

2018-07-20 05:47:48

题意 求$$\sum_1^n \sum_1^n \phi(gcd(i, j))$$ $T \leqslant 5000, N \leqslant 10^7$ Sol 延用BZOJ4407的做法 化到最后可以得到 $$\sum_{T = 1}^n \frac{n}{T} \frac{n}{T} \sum_{d \mid T}^n \phi(d) \mu(\frac{T}{d})$$ 后面的那个是积性函数，直接筛出来 注意这个...

2018-07-20 05:47:47

Description 给下N,M,K.求 感觉好迷茫啊，很多变换看的一脸懵逼却又不知道去哪里学。一道题做一上午也是没谁了，， 首先按照套路反演化到最后应该是这个式子 $$ans = \sum_{d = 1}^n d^k \sum_{i = 1}^{\frac{n}{d}} \frac{n}{di} \frac{m}{di} \mu(i)$$ 这样就可以$O(...

2018-07-19 05:35:41

Time Limit:10 Sec Memory Limit:128 MB Submit:386 Solved:296 [Submit][Status][Discuss] Description Mato同学最近正在研究一种矩阵，这种矩阵有n行n列第i行第j列的数为gcd(i,j)。 例如n=5时，矩阵如下： 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 2 1 4 1 1 1 1 1 5 Mato想...

2018-07-19 05:35:40

Time Limit:10 SecMemory Limit:256 MB Submit:557Solved:318 [Submit][Status][Discuss] Description 给定n个正整数a1,a2,,an，求 的值（答案模10^9+7）。 Input 第一行一个正整数n。 接下来n行，每行一个正整数，分别为a1,a2,,an。 Output 仅一行答案。 Sample Input...

2018-07-19 05:35:38

题目背景 提示：原 P1829 半数集问题 已经迁移至 P1028 数的计算 题目描述 今天的数学课上，Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数a和b，LCM(a, b)表示能同时整除a和b的最小正整数。例如，LCM(6, 8) = 24。 回到家后，Crash还在想着课上...

2018-07-19 05:35:36

Description 给定一些数，求这些数中两个数的异或值最大的那个值 Input 多组数据。第一行为数字个数n，1 = n = 10 ^ 5。接下来n行每行一个32位有符号非负整数。 Output 任意两数最大异或值 Sample Input 3379 Sample Output 14 Hint Source CSGrandeur的数据结构习题...

2018-07-18 01:15:47

Time Limit:5 Sec Memory Limit:128 MB Submit:3860 Solved:1751 [Submit][Status][Discuss] Description 根据一些书上的记载，上帝的一次失败的创世经历是这样的： 第一天， 上帝创造了一个世界的基本元素，称做元。 第二天， 上帝创造了一个新的元素，称作。被定义为...

2018-07-18 01:15:44

二分是一种常用而且非常精妙的算法，常常是我们解决问题的突破口。二分的基本用途是在 单调序列 或 单调函数 中做查找操作。因此，当问题的答案具有单调性时，就可以通过二分把求解转化为判定 （根据复杂度理论，判定的难度小于求解） 。进一步的，我们还可以通过三分...

2018-07-18 01:15:42

http://codeforces.com/contest/757/problem/E 题意 Sol 非常骚的一道题 首先把给的式子化一下，设$u = d$，那么$v = n / d$ $$f_r(n) = \sum_{d \mid n} \frac{f_{r - 1}(d) + f_{r - 1}(\frac{n}{d})}{2}$$ $$= \sum_{d\mid n} f_{r - 1}(d)$$ 很显然，这是$f_r(n)$...

2018-07-18 01:15:41