标签 - 亚线性筛

? 解题记录 ? ? SPOJ ? ? 亚线性筛 ?    2020-09-23 08:18:19    782    0    0
传送门 题意:计算σ0(i3)" role="presentation" style="position: relative;">σ0(i3)σ0(i3)\sigma_0(i^3)的前缀和 以前雅礼集训的时候就听说过这题,好像是洲阁筛板子? 但是如今世道不同了,Min_25" role="presentation" style="position: relative;">Min_25Min_25Min\_25筛可以把这种东西吊起来筛! 当p∈Prime,f(pc)=3c+1" role="present
? 解题记录 ? ? SPOJ ? ? 亚线性筛 ?    2020-09-23 08:18:17    545    0    0
传送门 题意:计算σ0(ik)\sigma_0(i^k)的前缀和 一道牛逼题目,Min_25Min\_25筛写的很简短。 当p∈Prime,f(pc)=ck+1p\in Prime,f(p^c)=ck+1 且当p∈Prime,f(p)=k+1p\in Prime,f(p)=k+1 又因为前缀和∑ni=1k+1=n(k+1)\sum^n_{i=1}k+1=n(k+1)可以O(1)O(1) 直接Min_25Min\_25筛就行了,复杂度O(1011)O(10^{11})能过。 #include<cstdio>#include<algorithm>#
? 解题记录 ? ? Topcoder ? ? 动态规划 ? ? 数位dp ? ? 亚线性筛 ?    2019-03-04 20:16:33    465    0    0
Easy DigitStringDiv1 题意:给一个串s" role="presentation" style="position: relative;">sss,给定数x" role="presentation" style="position: relative;">xxx,现在擦除s" role="presentation" style="position: relative;">sss的一些字符,问有多少种擦除方法使得s" role="presentation" style="position: relative;">sss组成的数字严格大于x" role=
? 解题记录 ? ? 亚线性筛 ? ? BZOJ ?    2018-12-19 20:53:45    479    0    0
Description 给定n,m,求 模10^9+7的值。 Input 仅一行,两个整数n,m。 Output 仅一行答案。 Sample Input 100000 1000000000 Sample Output 857275582 数据规模: 1&lt;=n&lt;=105&#xFF0C;1&lt;=m&lt;=109" role="presentation" style="position: relative;">1<=n<=105,1<=m<=109
? 解题记录 ? ? 莫比乌斯函数 ? ? 亚线性筛 ?    2018-12-09 17:39:22    175    0    0
Problem Description There is a function f(x),which is defined on the natural numbers set N,satisfies the following eqaution N2−3N+2=∑d|Nf(d) calulate ∑Ni=1f(i) mod 109+7. Input the first line contains a positive integer T,means the number of the test cases. next T lines there is a number
? 解题记录 ? ? 杂OJ ? ? 亚线性筛 ?    2018-01-23 11:27:17    439    0    0
给出一个数N,输出小于等于N的所有数,两两之间的最大公约数之和。 相当于计算这段程序(程序中的gcd(i,j)表示i与j的最大公约数): 由于结果很大,输出Mod 1000000007的结果。 G=0;for(i=1;i<N;i++)for(j=1;j<=N;j++){ G = (G + gcd(i,j)) % 1000000007;} Input 输入一个数N。(2 <= N <= 10^10) Output 输出G Mod 1000000007的结果。 Input示例 100 Output示例 31080 推导: &am
? 解题记录 ? ? 杂OJ ? ? 亚线性筛 ?    2018-01-19 13:12:12    835    0    0
出一个数N,输出小于等于N的所有数,两两之间的最小公倍数之和。 相当于计算这段程序(程序中的lcm(i,j)表示i与j的最小公倍数): 由于结果很大,输出Mod 1000000007的结果。 G=0;for(i=1;i< N;i++)for(j=1;j<=N;j++){ G = (G + lcm(i,j)) % 1000000007;} Input 输入一个数N。(2 <= N <= 10^10) Output 输出G Mod 1000000007的结果。 Input示例 4 Output示例 72 推导: G(
? 解题记录 ? ? 杂OJ ? ? 亚线性筛 ?    2018-01-18 13:56:15    448    0    0
莫比乌斯函数,由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)(miu(n))作为莫比乌斯函数的记号。具体定义如下: 如果一个数包含平方因子,那么miu(n) = 0。例如:miu(4), miu(12), miu(18) = 0。 如果一个数不包含平方因子,并且有k个不同的质因子,那么miu(n) = (-1)^k。例如:miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) = 1。 给出一个区间[a,b],S(a,b) = miu(a) + miu(a + 1) + ...... miu(b)。 例如:S(3