首先是杜教筛套路式子
求
其中n很大一般
一般做法：
然后就发现右边等式最后一项除以
而
先是一道模板题
BZOJ3944
Description
给定一个正整数N(N<=
)求 Input
一共
行 第 行为数据组数 第 行每行一个非负整数N，代表一组询问 Output
一共T行，每行两个用空格分隔的数ans1,ans2
对于这道题可以知道
Code
1 | inline ll solve(int opt,unsigned x){ |
傻逼题讲完了T.T
BZOJ3930
Description
我们知道，从区间[L,H]（L和H为整数）中选取N个整数，总共有
种方案。小z很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的N个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小z会告诉你一个整数K，你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大，你只需要输出其除以1000000007的余数即可。 ### Input 输入一行，包含4个空格分开的正整数，依次为N，K，L和H。 ### Output 输出一个整数，为所求方案数。 Sample Input
Sample Output
HINT
样例解释 所有可能的选择方案：(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4) 其中最大公约数等于2的只有3组：(2, 2), (2, 4), (4, 2) 对于100%的数据，
一看这数据范围就懵逼了=.=
先
然后看上去要杜教筛不过
一堆差不超过
区间任选
并且选的这
所以选的方案要减去这个区间的数的个数（刚好这么多种所有数都一样的方案）
还有个特判为区间是否包含1，包含
Code
1
2
3
4
5
6
7
8
9
10
11
12
inline int getf(int x){
int lt=(L%x)?L/x+1:L/x,rt=R/x;
return add(qpow(rt-lt+1,N),-rt+lt-1);
}
int main(){
pre();
read(N);read(K);read(L);read(R);
L=L%K?L/K+1:L/K;R/=K;n=R-L;
for (int i=1;i<=n;i++)
ans=add(ans,mul(mu[i],getf(i)));
if (L<=1 && 1<=R) ans=add(ans,1);
}
1 | inline int getf(int x){ |
BZOJ3529
Description
有一张
的数表，其第 行第 列 的数值为 能同时整除 和 的所有自然数之和。给定 , 计算数表中不大于 的数之和。 ### Input 输入包含多组数据。 输入的第一行一个整数 表示测试点内的数据组数 接下来 行，每行三个整数 描述一组数据。 ### Output 对每组数据，输出一行一个整数，表示答案模 的值。 Sample Input
2
3
4 4 3
10 10 5Sample Output
2
148
好像很难搞=.=不过1e5数据范围可以不用杜教筛 吼啊
写成数学符号就是
先考虑简化版问题：不考虑a的影响怎么做
首先约数和
假设
所以答案就是
然后考虑怎么加入a的限制
emmm
N,M才
动态维护前缀和的数据结构比如说树状数组
模自然溢出和
然后这题就结束了
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
inline void pre(){
mu[1]=1;t[1]=1;F[1].xx=1;
for (int i=2;i<=MAXN;i++){
if (!vis[i]) prime[++cnt]=i,vis[i]=i,F[i].xx=i+1,t[i]=i+1,mu[i]=-1;
for (int j=1;j<=cnt && i*prime[j]<=MAXN;j++){
vis[i*prime[j]]=1;
if (i%prime[j]) {
mu[i*prime[j]]=-mu[i];
F[i*prime[j]].xx=F[i].xx*1+prime[j]),t[i*prime[j]]=prime[j]+1;
}else {
mu[i*prime[j]]=0;
t[i*prime[j]]=t[i]*prime[j]+1;
F[i*prime[j]].xx=F[i].xx/t[i]*t[i*prime[j]];
break;
}
}
}
for (int i=1;i<=MAXN;i++) F[i].yy=i;
}
inline void fadd(int x){
for (int i=1;i*F[x].yy<=MAXN;i++)
add(i*F[x].yy,F[x].xx*mu[i]);
}
//这里省略
sort(q+1,q+N+1); sort(F+1,F+MAXN+1);
for (int i=1,j=0;i<=N;i++){
while (j<MAXN&&F[j+1].xx<=q[i].a) fadd(++j);
n=q[i].n;m=q[i].m;
if (n>m) swap(n,m);
for (int l=1,r=1;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans[q[i].id]+=(n/l)*(m/l)*(query(r)-query(l-1));
}
}
1 | inline void pre(){ |
BZOJ4652
Description
牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在
进制下，一个数的小数部分是纯循环的，那么它就是美的。现在，牛牛想知道：对于已知的十进制数 和 ，在 k 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 表示,其中 ，且 是整数。一个数是纯循环的，当且仅当其可以写成以下形式： 其中， 是一个整数， ；对于 ， 是 进制下的一位数字。例如，在十进制下， 是纯循环的，它可以用 等分数表示；在十进制下， 则不是纯循环的，它可以用 等分数表示。需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 的循环或是 的循环；而一个小数部分非 的有限小数不是纯循环的。 ### Input 只有一行，包含三个十进制数N,M,K意义如题所述,保证 ### Output 一行一个整数，表示满足条件的美的数的个数。 Sample Input
Sample Output
HINT
满足条件的数分别是： 1/1=1.0000…… 1/3=0.3333…… 2/1=2.0000…… 2/3=0.6666…… 1/1 和 2/2 虽然都是纯循环小数，但因为它们相等，因此只计数一次；同样，1/3 和 2/6 也只计数一次。
啥，纯循环小数，没听过0.0
首先这题很显然可以看出是要求一些分子分母互质的数的个数(不互质的会重复出现)
先不管那么多式子写起来
还有一个可能是对的不会证得就是对于一个纯循环小数
还是以找找规律打表
猜测推理我们发现这东西应该是要求分母与k互质
具体为什么=.=
证明From 神仙网友
我们先来回想一下，我们是怎样使用除法来判断一个分数
又由于题目要求值不重复，那么我们可以得到
所以事情变成了我们熟悉的样子
然后开始乱搞
所以开始打暴力可能需要分别计算
所以只需预处理int f(int x){return (x/K)*F[K]+F[x%K];}
如果是这样这题就不会是最后一道了
很简单的例子比如
于是开始硬刚
！！！
所以得到
然后又变成简单递归题了，复杂度
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
map<pii,int>MA;
inline int f(int x){return (x/K)*F[K]+F[x%K];}
inline int g(int x,int k){//比一般杜教筛多了个参数0.0
if ((k==1 && x<MAXN)|| !x) return sum[x];
if (MA[pii(x,k)]) return MA[pii(x,k)];
int ret=0;
if (k==1){
ret++;
for (int i=2,j=2;i<=x;i=j+1){
j=x/(x/i);
ret-=(j-i+1)*g(x/i,1);
}
}else{
for (int i=1;i*i<=k;i++) if (!(k%i)){//这里也只用枚举到sqrt(k)，因为因数是成对的
if (mu[i])ret+=g(x/i,i); //这里防止mu[i]等于0白算一堆
if (mu[k/i] && (i*i^k)) ret+=g(x/(k/i),k/i);//i*i！=k才再算不然贡献算两遍
}
}
return MA[pii(x,k)]=ret;
}
//这里还是省略防止ctrl+c
pre();
n=min(N,M);
for (int i=1,j=1;i<=n;i=j+1){
j=min(N/(N/i),M/(M/i));
cur=S(j,K);
ans+=(ll)(cur-lst)*f(M/i)*(N/i);
lst=cur;
}
1 | map<pii,int>MA; |
总结
杜教筛是看上去很难实际上也没那么难的东西，希望今天大家都听懂了=.=