杜教筛与卷积

/*
常见数论函数
e(n)=[n=1]
1(n)=1
id(n)=n
d(n)=sum{1} (1<=i<=n&&i|n)
SIG(n)=sum{i} (1<=i<=n&&i|n)

常见关系
e=u*1
d=1*1
SIG=id*1
id=phi*1

杜教筛
g(1->i->n)*f(1->n/i) = (g*f)(1->n)
g(1)*f(1->n) = (g*f)(1->n) - g(2->i->n)*f(1->n/i)

phi*I = id
I(1)*phi(1->n) = (I*phi)(1->n) - I(2->i->n)*phi(1->n/i)
phi(1->n) = id(1->n) - phi(1->n/i)
phi(1->n) = n*(n+1)/2 - phi(1->n/i), (2<=i<=n)g
*/

//杜教筛求 phi(n) 前缀和
ll sum_phi(ll n){// 2e9 is ok
    static map<ll,ll> mp;
    if(n<maxn) return PHI[n];
    ll ret=mp[n];
    if(ret!=0) return ret;
    ret=n*(n+1)/2;
    for(ll i=2,ed;i<=n;i=ed+1){
        ed=n/(n/i);
        ret-=(ed-i+1)*sum_phi(n/i);
    }
    if(n>maxn) mp[n]=ret;
    return ret;
}