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=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=998630; ll n; ul miu[N],sig[N],sq[N]; bool vis[N]; int divcnt[N],pri[N+5],tot; ll a[200005]; ll up; void sieve(ll n){ miu[1]=1;sig[1]=1; for(reg i=2;i<=n;++i){ if(!vis[i]){ pri[++tot]=i; miu[i]=-1; sig[i]=2; divcnt[i]=1; } for(reg j=1;j<=tot;++j){ if(pri[j]*i>n) break; vis[pri[j]*i]=1; if(i%pri[j]==0){ divcnt[i*pri[j]]=divcnt[i]+1; miu[i*pri[j]]=0; sig[i*pri[j]]=sig[i]/(divcnt[i]+1)*(divcnt[i]+2); break; } divcnt[i*pri[j]]=1; miu[i*pri[j]]=-miu[i]; sig[i*pri[j]]=sig[i]*sig[pri[j]]; } } sq[1]=1; for(reg i=2;i<=n;++i) { sq[i]=miu[i]*miu[i]; sq[i]+=sq[i-1]; sig[i]+=sig[i-1]; } } ul M(ll n){ if(n<=up) return sq[n]; ul ret=0; for(reg i=1;(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=0; for(ll i=1,x=0;i<=n;i=x+1){ x=(n/(n/i)); ret=ret+(x-i+1)*(n/i); } // cout<<" S "<<ret<<endl; return ret; } ul solve(ll n){ ul ret=0; for(ll i=1,x=0;i<=n;i=x+1){ x=(n/(n/i)); ret=ret+(M(x)-M(i-1))*S(n/i); // cout<<"["<<i<<","<<x<<"] : "<<ret<<endl; } return ret; } int main(){ int t; rd(t); ll mx=0; for(reg i=1;i<=t;++i) scanf("%lld",&a[i]),mx=max(mx,a[i]); if(mx<=N-5){ up=mx; sieve(up); }else{ up=N-5; sieve(up); } for(reg i=1;i<=t;++i){ printf("%llu\n",solve(a[i])); } return 0; } } signed main(){ Miracle::main(); return 0; } /* 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=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void ot(T x){x/10?ot(x/10):putchar(x%10+'0');} 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+6; const int U=2e6+1; const int K=2; int vis[N],pri[N],tot; int cnt; ll n; il void sieve(int n){ for(reg i=2;i<=n;++i){ if(!vis[i]){ pri[++tot]=i; } for(reg j=1;j<=tot;++j){ if(i*pri[j]>n) break; vis[i*pri[j]]=1; if(i%pri[j]==0) break; } } } ul f[N]; ll id1[N+233],id2[N+233]; ll val[3*N],num; il ul G(ll M,int j){ // cout<<" G "<<M<<" "<<j<<endl; if(M<=1||M<pri[j]) return 0; int id=(M<=U)?id1[M]:id2[n/M]; ul ret=f[id]-(ul)(j-1)*(K+1); 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=1;now*pri[t]<=M;++e,now*=pri[t]){ // cout<<" ee "<<e<<endl; ret=ret+(ul)(K*e+1)*G(M/now,t+1)+(ul)(K*e+K+1); } } // cout<<" ret "<<M<<" "<<j<<" : "<<ret<<endl; return ret; } void clear(){ num=0;cnt=0; } int main(){ int T; rd(T); sieve(N-5); while(T--){ rd(n); if(n==1){ puts("1"); continue; } int ban=sqrt(n); cnt=lower_bound(pri+1,pri+tot+1,ban)-pri; // cout<<" cnt "<<cnt<<endl; for(ll i=1,x=0;i<=n;i=x+1){ 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=1;i<=num;++i){ f[i]=(ul)(K+1)*(val[i]-1); } for(reg j=1;j<=cnt;++j){ // cout<<" j ------------- "<<j<<endl; for(reg i=1;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+1)*(j-1)); } } // for(reg i=1;i<=num;++i){ // cout<<i<<" : "<<f[i]<<endl; // } printf("%llu\n",(ul)G(n,1)+1); clear(); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/3/9 16:39:18 */
测试发现
Min_25在n<=1e12时候基本都是比杜教筛快。
在N<=1e9时候更是秒出
但是数据组数多了以后，杜教筛记忆化的优势就体现明显了。