UOJ Logo FoolMike的博客

博客

NOI2016循环之美卡常程序,求复杂度证明

2016-12-02 14:11:08 By FoolMike

TLE代码来自http://uoj.ac/submission/110599

AC代码来自http://uoj.ac/submission/110933

推导如下:

设答案为ans,莫比乌斯函数为u,则

ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (gcd(i,j)==1&&gcd(j,k)==1) ans++;

莫比乌斯反演得

ans=0;
for (int j=1;j<=m;j++)
if (gcd(j,k)==1){
    for (int d=1;d<=j;d++)
    if (!(j%d)) ans+=u[d]*(n/d);
}

莫比乌斯反演得

ans=0;
for (int d=1;d<=n;d++)
if (gcd(d,k)==1){
    for (int j=d;j<=m;j+=d)
    if (gcd(j,k)==1) ans+=u[d]*(n/d);
}

定义函数如下:

int f(int x){
    int ans=0;
    for (int i=1;i<=k;i++)
    if (!(k%i)) ans+=u[i]*(x/i);
    return ans;
}

莫比乌斯反演得

ans=0;
for (int d=1;d<=n;d++)
if (gcd(d,k)==1) ans+=u[d]*(n/d)*f(m/d);

枚举t=gcd(d,k),莫比乌斯反演得

for (int t=1;t<=k;t++)
if (!(k%t)&&u[t]){
    for (int d=t;d<=n;d+=t)
    ans+=u[t]*u[d]*(n/d)*f(m/d);
}

分块,设x=n/d,y=m/d。

for (int t=1;t<=k;t++)
if (!(k%t)&&u[t]){
    for (int d=t;d<=n;d+=t)
    ans+=x*f(y)*u[t]*u[d];
}

由积性得

for (int t=1;t<=k;t++)
if (!(k%t)&&u[t]){
    for (int d=t;d<=n;d+=t)
    if (gcd(d/t,t)==1) ans+=x*f(y)*u[d/t];
}

定义函数如下:

int sum(int x){
    int ans=0;
    for (int i=1;i<=x;i++)
    if (gcd(i,k)==1) ans+=u[i];
    return ans;
}

那么上述过程为

for (int t=1;t<=k;t++)
if (!(k%t)&&u[t]) ans+=x*f(y)*sum(n/t,k);

对sum函数,枚举gcd,莫比乌斯反演得

int sum(int x,int k){
    int ans=0;
    for (int t=1;t<=k;t++)
    if (!(t%k)){
        for (int d=1;d<=n/t;d++) ans+=u[t*d];
    }
    return ans;
}

由积性得

int sum(int x,int k){
    int ans=0;
    for (int t=1;t<=k;t++)
    if (!(t%k)){
        for (int d=1;d<=n/t;d++) ans+=sum(n/t,t);
    }
    return ans;
}

上述枚举为了易于理解,复杂度较高

不知道sum函数的复杂度是多少,希望神犇证明一下这个函数的时间复杂度。

这个似乎复杂度还可以,只是被卡常了。

在原代码基础上打了个小范围的记忆化就AC了。

TLE代码如下:

#include<cstdio>
const int N=1e6+10,SIZE=1e6;
typedef long long ll;
int n,m,k,u[N],p[N],cnt,s[N],v[2],q[N],size;
bool hash[N],vis[2][N];
ll su[2][N];
ll get_s(int x,bool y){
    return x<=SIZE?s[x]:su[y][v[y]/x];
}
void solve(int x,bool y){
    if (x<=SIZE) return;
    int t=v[y]/x;
    if (vis[y][t]) return;
    vis[y][t]=1;su[y][t]=1;
    int l,r=1;
    while (r<x){
        l=r+1;r=x/(x/l);
        solve(x/l,y);
        su[y][t]-=get_s(x/l,y)*(r-l+1);
    }
}
ll sum(int x,int k,bool y){//O(玄学) 
    if (!x) return 0;
    if (k==1) return get_s(x,y);
    ll ans=0;
    for (int i=1;i<=size&&q[i]<=k&&q[i]<=x;i++){
        int t=q[i];
        if (!(k%t)) ans+=sum(x/t,t,y);
    }
    return ans;
}
ll f(int x){//O(16)
    ll ans=0;
    for (int i=1;i<=size;i++) ans+=u[q[i]]*(x/q[i]);
    return ans;
}
int main()
{
    //freopen("cyclic.in","r",stdin);
    //freopen("cyclic.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    //杜教筛 
    u[1]=1;v[0]=n;v[1]=m;
    for (int i=2;i<=SIZE;i++){
        if (!hash[i]) p[++cnt]=i,u[i]=-1;
        for (int j=1;j<=cnt&&i*p[j]<=SIZE;j++){
            hash[i*p[j]]=1;
            if (i%p[j]) u[i*p[j]]=-u[i];
                else{u[i*p[j]]=0;break;}
        }
    }
    for (int i=1;i<=SIZE;i++) s[i]=s[i-1]+u[i];
    solve(n,0);solve(m,1);
    //质因子分解 
    for (int i=1;i<=k;i++)
    if (u[i]&&!(k%i)) q[++size]=i;
    //分块 
    int l=0,r=0;
    ll last=0,ans=0;
    while (l<n&&l<m){
        r=n/(n/(l+1));
        bool tag=0;//表示从n或m转移而来
        if (m/(m/(l+1))<r) r=m/(m/(l+1)),tag=1;
        int x=n/r,y=m/r;
        ll now=sum(r,k,tag);
        ans+=x*(now-last)*f(y);
        l=r;last=now;
    }
    printf("%lld\n",ans);
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。