dwjshift's Blog

bzoj2154 & bzoj2693

| Comments

治疗公式恐惧症用

先是bzoj2154。

再令

则有

那么

用分块的方法可以在分别求出,总复杂度为

接着是bzoj2693,其实就是上一题的多组数据版,但是每次询问的复杂度显然会TLE。于是继续推式子。

积性函数如下性质:若均为积性函数,则函数也是积性函数;若为积性函数,则函数也是积性函数。因此,是积性函数,那么就可以用线性筛预处理其前缀和了。
另外,当时,容易发现新增的约数的值为,故
同样,通过分块就使单次询问复杂度为,故总复杂度为

code

bzoj2154

#include <cstdio>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

typedef long long LL;
const LL mod=20101009;
int n,m,prm[700000],tot,mu[10000100];
LL sum[10000100],ans;
bool flag[10000100];

void get()
{
    mu[1]=sum[1]=1;
    repu(i,2,n)
    {
        if (!flag[i])
            mu[prm[++tot]=i]=-1;
        for (int j=1; j<=tot && i*prm[j]<=n; ++j)
        {
            flag[i*prm[j]]=1;
            if (!(i%prm[j]))
                break;
            mu[i*prm[j]]=-mu[i];
        }
        sum[i]=(LL(i)*i%mod*mu[i]+sum[i-1]+mod)%mod;
    }
}

LL calc2(LL x,LL y)
{
    return (x*(x+1)/2%mod)*(y*(y+1)/2%mod)%mod;
}

LL calc1(int x,int y)
{
    LL ret=0;
    for (int i=1,t; i<=x; i=t+1)
    {
        t=min(x/(x/i),y/(y/i));
        ret=(ret+(sum[t]-sum[i-1]+mod)*calc2(x/i,y/i))%mod;
    }
    return ret;
}

int main()
{
    scanf("%d%d",&n,&m);
    if (n>m)
        swap(n,m);
    get();
    for (int i=1,t; i<=n; i=t+1)
    {
        t=min(n/(n/i),m/(m/i));
        ans=(ans+LL(i+t)*(t-i+1)/2%mod*calc1(n/i,m/i))%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

bzoj2693

#include <cstdio>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

typedef long long LL;
const LL mod=100000009;
const int maxn=1e7;
int k,n,m,prm[700000],tot;
LL sum[10000100],ans;
bool flag[10000100];

void get()
{
    sum[1]=1;
    repu(i,2,maxn)
    {
        if (!flag[i])
            sum[prm[++tot]=i]=(1-i+mod)%mod;
        for (int j=1; j<=tot && i*prm[j]<=maxn; ++j)
        {
            flag[i*prm[j]]=1;
            if (!(i%prm[j]))
            {
                sum[i*prm[j]]=sum[i];
                break;
            }
            sum[i*prm[j]]=sum[i]*sum[prm[j]]%mod;
        }
    }
    repu(i,2,maxn)
        sum[i]=(sum[i]*i+sum[i-1])%mod;
}

LL calc(LL x,LL y)
{
    return (x*(x+1)/2%mod)*(y*(y+1)/2%mod)%mod;
}

int main()
{
    get();
    for (scanf("%d",&k); k--;)
    {
        scanf("%d%d",&n,&m),ans=0;
        if (n>m)
            swap(n,m);
        for (int i=1,t; i<=n; i=t+1)
        {
            t=min(n/(n/i),m/(m/i));
            ans=(ans+calc(n/i,m/i)*(sum[t]-sum[i-1]+mod))%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Comments

comments powered by Disqus