SPOJ DIVCNTK

Link

Solution

使用min_25筛
由于求h的过程都只会用到[\frac ni]集合中的点,那么求g的过程中把[\frac ni]构成的集合求出来,对于这个集合的所有点分层递推(递推过程中需要用到的g也属于[\frac ni]集合),就可以求出g(i,|P|)
然后递归求h,并不需要记忆化。边界见代码。

Code

typedef unsigned long long qword;

const int N=2e5,XN=N+11;

int prime[XN],pcnt;
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i])
            prime[++pcnt]=i;
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

long long n,k;
int lim,psz;

struct Identifier {
    int id[2][XN*2],cnt;
    int &operator [](long long x) {
        int &res=x<=lim?id[0][x]:id[1][n/x];
        if(res==0)
            res=++cnt;
        return res;
    }
}id;

qword g[XN*2];

qword H(long long n,int m) {
    if(n<=1 || m>psz)
        return 0;
    qword res=(k+1)*(g[id[n]]-m+1);
    for(int i=m;i<=psz && (long long)prime[i]*prime[i]<=n;++i) {
        long long pt=prime[i];
        for(int t=1;pt*prime[i]<=n;++t,pt*=prime[i])
            res+=H(n/pt,i+1)*(k*t+1)+(k*(t+1)+1);//id[n/pt]
    }
    return res;
}

void Work() {
    lim=sqrt(n)+0.5;
    id.cnt=0;
    for(int i=0;i<=lim;++i)
        id.id[0][i]=id.id[1][i]=0;
    psz=std::lower_bound(prime+1,prime+1+pcnt,lim)-prime;
    static long long kp[XN*2];int kpc=0;
    for(long long l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        g[id[kp[++kpc]=n/l]]=n/l-1;
    }
    for(int j=1;j<=psz;++j)
        for(int i=1;i<=kpc && (long long)prime[j]*prime[j]<=kp[i];++i)
            g[id[kp[i]]]-=g[id[kp[i]/prime[j]]]-(j-1);
    std::cout<<H(n,1)+1<<'\n';
}

int main() {
    Prep();
    int T;fin>>T;
    while(T--) {
        fin>>n>>k;
        Work();
    }
    return 0;
}

胡扯min_25筛

记质数集合为P

Problem

以低于线性的复杂度求一类积性函数的和,函数需满足
f(p),f(p^k)(p\in P)很好求。

Solution

{\rm Min}(x)x的最小质因子。

g

g(n,i)=\sum f(x)[ {x\le n {\ \rm and\ } (x \in P {\ \rm or\ } {\rm Min}(x)>P_i) } ]
n < P_i^2时,g(n,i)=g(n,i-1),因为最小的{\rm Min}(x)= P_i的合数就是P_i^2
否则,考虑从g(n,i-1)中减去{\rm Min}(x)= P_i的合数的贡献,也就是\sum f(x)[{x\le n,{\rm Min}(x)=P_i}],提出f(P_i),式子变成了f(P_i)(g([\frac n{P_i}],i-1)-\sum_{j=1}^{i-1}f(P_j))
\therefore
g(n,i)= \begin{cases} g(n,i-1)&,n < P_i^2\\ g(n,i-1)-f(P_i)(g([\frac n{P_i}],i-1)-\sum_{j=1}^{i-1}f(P_j))&,\text{otherwise} \end{cases}

h

h(n,i)=\sum_{j=1}^nf(j)[{\rm Min}(j)\ge P_i]
对于h(n,i)n以内质数的贡献是g(n,|P|)-\sum_{j=1}^{i-1}f(P_j)
现在考虑合数的贡献。
枚举合数的最小质因子P_j,那么最小质因子为P_j的合数的贡献就是\sum_{t\ge 1,P_j^{t+1}\le n}(h([\frac n{P_j^t}],j+1)f(P_j^t)+f(P_j^{t+1}))
因此
h(n,i)=g(n,|P|)-\sum_{j=1}^{i-1}f(P_j)+\sum_{j\ge i}\sum_{t\ge 1,P_j^{t+1}\le n}(h([\frac n{P_j^t}],j+1)f(P_j^t)+f(P_j^{t+1}))
答案就是h(n,1)了。

Tips

具体实现的时候,g不一定求\sum f(x)[ {x\le n {\ \rm and\ } (x \in P {\ \rm or\ } {\rm Min}(x)>P_i) } ],求出的g只要能使得上式可以被很快求出即可。

[zoj4056][ICPC 2018 Qingdao Online]Press the Button

Link

Solution

问题最后是求一个长度为t的数轴上有多少对相邻的关键点距离\ge v,关键点是所有ac的倍数的点。
假设a < c
如果a < v则不存在
否则
考虑c的倍数与它后面相邻的a的倍数的距离
根据根据鸽巢原理,至多c步,这个距离就会开始循环
然后把t分成三部分:
不在循环+循环部分+一段没循环完的部分
细节巨多写到脑壳疼
~正解是模拟到{\rm lcm}(a,b),直接判断,然后循环~

Code

const int XN=1e6+11;
void Work() {
    long long v,t,a,b,c,d;
    fin>>a>>b>>c>>d>>v>>t;
    long long Ans=(long long)((t/a)+1)*b+(long long)((t/c)+1)*d-1;
    if(a>v && c>v) {
        if(a>c)
            std::swap(a,c);
        static int us[XN],ut;
        static long long crec[XN],prec[XN];
        ++ut;long long cnt=0,pc=0,py=0;
        for(;;pc+=c) {
            long long x=(pc/a)*a,y=x+a; 
            cnt+=((pc-x)>v)+((y-pc)>v)+(x-py)/a;
            py=y;
            if(us[y-pc]==ut)
                break;
            us[y-pc]=ut;
            crec[y-pc]=cnt;
            prec[y-pc]=py;
        }
        if(t>prec[py-pc]) {
            long long circnt=cnt-crec[py-pc],cirlen=py-prec[py-pc];
            Ans-=circnt*((t-prec[py-pc])/cirlen)+crec[py-pc];
            py+=((t-prec[py-pc])/cirlen-1)*cirlen;
            pc=(py/c+1)*c;
        } else {
            py=pc=0;
        }
        if(pc<=t)
            for(;;pc+=c) {
                long long x=(pc/a)*a,y=x+a;
                Ans-=((pc-x)>v)+(x-py)/a;
                if(y<=t) {
                    Ans-=((y-pc)>v);
                }
                py=y;
                if(pc+c>t)
                    break;
            }
        if(py<t)
            Ans-=(t-py)/a;
    }
    fout<<Ans<<'\n';
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}