DIVCNT2&&3 - Counting Divisors

时间:2022-09-17 13:18:41

DIVCNT2 - Counting Divisors (square)

DIVCNT3 - Counting Divisors (cube)

杜教筛

[学习笔记]杜教筛

(其实不算是杜教筛,类似杜教筛的复杂度分析而已)

你要大力推式子:

把约数个数代换了

把2^质因子个数 代换了

构造出卷积,然后大于n^(2/3)还要搞出约数个数的式子和无完全平方数的个数的容斥。。。

。。。。

然后恭喜你,spoj上过不去。。。

bzoj能过:

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define ul unsigned long long
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=;
ll n;
ul miu[N],sig[N],sq[N];
bool vis[N];
int divcnt[N],pri[N+],tot;
ll a[];
ll up;
void sieve(ll n){
miu[]=;sig[]=;
for(reg i=;i<=n;++i){
if(!vis[i]){
pri[++tot]=i;
miu[i]=-;
sig[i]=;
divcnt[i]=;
}
for(reg j=;j<=tot;++j){
if(pri[j]*i>n) break;
vis[pri[j]*i]=;
if(i%pri[j]==){
divcnt[i*pri[j]]=divcnt[i]+;
miu[i*pri[j]]=;
sig[i*pri[j]]=sig[i]/(divcnt[i]+)*(divcnt[i]+);
break;
}
divcnt[i*pri[j]]=;
miu[i*pri[j]]=-miu[i];
sig[i*pri[j]]=sig[i]*sig[pri[j]];
}
}
sq[]=;
for(reg i=;i<=n;++i) {
sq[i]=miu[i]*miu[i];
sq[i]+=sq[i-]; sig[i]+=sig[i-];
}
}
ul M(ll n){
if(n<=up) return sq[n];
ul ret=;
for(reg i=;(ll)i*i<=n;++i){
ret=ret+miu[i]*(n/(i*i));
}
//cout<<" M "<<ret<<endl;
return ret; }
ul S(ll n){
if(n<=up) return sig[n];
ul ret=;
for(ll i=,x=;i<=n;i=x+){
x=(n/(n/i));
ret=ret+(x-i+)*(n/i);
}
// cout<<" S "<<ret<<endl;
return ret; }
ul solve(ll n){
ul ret=;
for(ll i=,x=;i<=n;i=x+){
x=(n/(n/i));
ret=ret+(M(x)-M(i-))*S(n/i);
// cout<<"["<<i<<","<<x<<"] : "<<ret<<endl;
}
return ret;
}
int main(){
int t;
rd(t);
ll mx=;
for(reg i=;i<=t;++i) scanf("%lld",&a[i]),mx=max(mx,a[i]);
if(mx<=N-){
up=mx;
sieve(up);
}else{
up=N-;
sieve(up);
}
for(reg i=;i<=t;++i){
printf("%llu\n",solve(a[i]));
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/3/6 21:18:05
*/

Min_25筛

sigma(i^3)是积性函数!

没了。

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define ul unsigned long long
#define mk(a,b) make_pair(a,b)
#define int long long
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
template<class T>il void ot(T x){x/?ot(x/):putchar(x%+'');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) printf("%lld ",a[i]);putchar('\n');} namespace Miracle{
const int N=2e6+;
const int U=2e6+;
const int K=;
int vis[N],pri[N],tot;
int cnt;
ll n;
il void sieve(int n){
for(reg i=;i<=n;++i){
if(!vis[i]){
pri[++tot]=i;
}
for(reg j=;j<=tot;++j){
if(i*pri[j]>n) break;
vis[i*pri[j]]=;
if(i%pri[j]==) break;
}
}
}
ul f[N];
ll id1[N+],id2[N+];
ll val[*N],num;
il ul G(ll M,int j){
// cout<<" G "<<M<<" "<<j<<endl;
if(M<=||M<pri[j]) return ;
int id=(M<=U)?id1[M]:id2[n/M];
ul ret=f[id]-(ul)(j-)*(K+);
for(reg t=j;t<=cnt&&(ll)pri[t]*pri[t]<=M;++t){
ul now=pri[t];
// cout<<" mindiv "<<t<<" : "<<now<<endl;
for(reg e=;now*pri[t]<=M;++e,now*=pri[t]){
// cout<<" ee "<<e<<endl;
ret=ret+(ul)(K*e+)*G(M/now,t+)+(ul)(K*e+K+);
}
}
// cout<<" ret "<<M<<" "<<j<<" : "<<ret<<endl;
return ret;
}
void clear(){
num=;cnt=;
}
int main(){
int T;
rd(T);
sieve(N-);
while(T--){
rd(n);
if(n==){
puts("");
continue;
}
int ban=sqrt(n);
cnt=lower_bound(pri+,pri+tot+,ban)-pri;
// cout<<" cnt "<<cnt<<endl;
for(ll i=,x=;i<=n;i=x+){
x=(n/(n/i));
val[++num]=n/i;
if(n/i<=U) id1[n/i]=num;
else id2[x]=num;
}
// cout<<" num "<<num<<endl;
for(reg i=;i<=num;++i){
f[i]=(ul)(K+)*(val[i]-);
}
for(reg j=;j<=cnt;++j){
// cout<<" j ------------- "<<j<<endl;
for(reg i=;i<=num;++i){
if((ll)pri[j]*pri[j]>val[i]) break;
int fr=val[i]/pri[j]<=U?id1[val[i]/pri[j]]:id2[n/(val[i]/pri[j])];
//cout<<" fr "<<fr<<endl;
f[i]=f[i]-(f[fr]-(ul)(K+)*(j-));
}
}
// for(reg i=1;i<=num;++i){
// cout<<i<<" : "<<f[i]<<endl;
// }
printf("%llu\n",(ul)G(n,)+);
clear();
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/3/9 16:39:18
*/

测试发现

Min_25在n<=1e12时候基本都是比杜教筛快。

在N<=1e9时候更是秒出

但是数据组数多了以后,杜教筛记忆化的优势就体现明显了。

DIVCNT2&&3 - Counting Divisors的更多相关文章

  1. SPOJ 20713 DIVCNT2 - Counting Divisors &lpar;square&rpar;

    DIVCNT2 - Counting Divisors (square) #sub-linear #dirichlet-generating-function Let \sigma_0(n)σ​0​​ ...

  2. &lbrack;SPOJ&rsqb; DIVCNT2 - Counting Divisors &lpar;square&rpar; &lpar;平方的约数个数前缀和 容斥 卡常&rpar;

    题目 vjudge URL:Counting Divisors (square) Let σ0(n)\sigma_0(n)σ0​(n) be the number of positive diviso ...

  3. HDU 6069 Counting Divisors

    Counting Divisors Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Oth ...

  4. hdu 6069 Counting Divisors(求因子的个数)

    Counting Divisors Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Oth ...

  5. hdu 6069 Counting Divisors 筛法

    Counting Divisors Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Oth ...

  6. 2017 Multi-University Training Contest - Team 4 hdu6069 Counting Divisors

    地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=6069 题目: Counting Divisors Time Limit: 10000/5000 ...

  7. hdu6069 Counting Divisors 晒区间素数

    /** 题目:hdu6069 Counting Divisors 链接:http://acm.hdu.edu.cn/showproblem.php?pid=6069 题意:求[l,r]内所有数的k次方 ...

  8. HDU 6069 Counting Divisors —— 2017 Multi-University Training 4

    Counting Divisors Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Oth ...

  9. SPOJ &colon; DIVCNT2 - Counting Divisors &lpar;square&rpar;

    设 \[f(n)=\sum_{d|n}\mu^2(d)\] 则 \[\begin{eqnarray*}\sigma_0(n^2)&=&\sum_{d|n}f(d)\\ans&= ...

随机推荐

  1. Name-based virtual servers 给予名称的虚拟服务

    nginx first decides which server should process the request. Let’s start with a simple configuration ...

  2. 【&period;Net Core】获取绝对路径、相对路径

    一.绝对路径 1.获取应用程序运行当前目录Directory.GetCurrentDirectory(). System.IO命名空间中存在Directory类,提供了获取应用程序运行当前目录的静态方 ...

  3. 安装 SIP 服务器

    SIP服务器: OpenSIPS(Open SIP S erver)是SIP服务器的一个成熟的开源实现.OpenSIPS不仅仅是一个SIP代理/路由器,因为它包含应用程序级别的功能.作为SIP服务器的 ...

  4. pycharm中split的应用

    #input 字符串 “5+9” value = "5+9" v1,v2 = value.split("+")#意思是把加号前后的5和9分别赋值给v1,v2 v ...

  5. ESN 与 MEID

    ESN (Electronic Serial Numbers):电子序列号.在CDMA 系统中,是鉴别一个物理硬件设备唯一的标识.也就是说每个手机都用这个唯一的ID来鉴别自己, 就跟人的身份证一样.一 ...

  6. 外部盒模型大小固定 内部有边框div设置浮动时 缩放窗口内部div溢出的解决办法

    原因分析: chorme和firefox浏览器下当缩放窗口大小时,边框的计算宽度变大造成内部div宽度的计算宽度变大,外部div放不下内部div而溢出. 解决办法: 给内部div设置 box-sizi ...

  7. SSM数据库数据导出excel

    首先,这是我对自己的需求而使用的逻辑,若有可以完美的地方方便告诉下小白. apache的poi MAVEN <dependency> <groupId>org.apache.p ...

  8. JavaScript数据检测

    前言: 随着编程实践的增加,慢慢发现关于数据类型的检测至关重要.我认为程序就是为了处理数据和展示数据.所以,数据的检测对于编程来说也至关重要.因为只有符合我们预期的输入,才可能产生正确的输出.众所周知 ...

  9. 11&period;事件驱动events

    事件驱动events ==> events.EventEmitter, EventEmitter 的核心就是事件发射与事件监听器功能的封装更详细的 API 文档参见 http://nodejs. ...

  10. MSBI

    https://blog.csdn.net/fanyingnedu/article/details/78597207 Familiarity with Microsoft BI Stack - SSI ...