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
*/
View Code
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
*/
View Code
测试发现
Min_25在n<=1e12时候基本都是比杜教筛快。
在N<=1e9时候更是秒出
但是数据组数多了以后，杜教筛记忆化的优势就体现明显了。