2 solutions

  • 0
    @ 2024-5-18 9:23:49

    #include<bits/stdc++.h>

    using namespace std;

    #define il inline

    #define re register

    #define debug printf("Now is Line %d\n",LINE)

    #define file(a)

    freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)

    #define mod 1000000007

    il int read()

    {

    re int x=0,f=1;re char c=getchar();

    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}

    while(c>='0'&&c<='9') x=x*10+c-

    48,c=getchar();

    return x*f;

    }

    #define maxn 40000

    int

    mu[maxn+5],prim[maxn+5],vis[maxn+5],cnt,n, ans;

    signed main()

    {

    n=read()-1;

    if(!n) return puts("0"),0;

    mu[1]=1;

    for(re int i=2;i<=n;++i)

    {

    if(!vis[i]) prim[++cnt]=i,mu[i]=-1;

    for(re int j=1;j<=cnt;++j)

    {

    if(prim[j]*i>n) break;

    vis[prim[j]*i]=1;

    if(i%prim[j]==0) break;

    mu[i*prim[j]]=-mu[i];

    }

    }

    for(re int i=1;i<=n;++i) mu[i]+=mu[i-1];

    for(re int l=1,r;l<=n;l=r+1)

    {

    r=n/(n/l);

    ans+=(mu[r]-mu[l-1])(n/l)(n/r);

    }

    printf("%d",ans+2);

    return 0;

    }

    • 0
      @ 2024-5-18 9:21:44

      #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",LINE) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define mod 1000000007 il int read() { re int x=0,f=1;re char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x10+c-48,c=getchar(); return xf; } #define maxn 40000 int mu[maxn+5],prim[maxn+5],vis[maxn+5],cnt,n,ans; signed main() { n=read()-1; if(!n) return puts("0"),0; mu[1]=1; for(re int i=2;i<=n;++i) { if(!vis[i]) prim[++cnt]=i,mu[i]=-1; for(re int j=1;j<=cnt;++j) { if(prim[j]i>n) break; vis[prim[j]i]=1; if(i%prim[j]==0) break; mu[iprim[j]]=-mu[i]; } } for(re int i=1;i<=n;++i) mu[i]+=mu[i-1]; for(re int l=1,r;l<=n;l=r+1) { r=n/(n/l); ans+=(mu[r]-mu[l-1])(n/l)*(n/r); } printf("%d",ans+2); return 0; }

      • 1

      Information

      ID
      1140
      Time
      1000ms
      Memory
      125MiB
      Difficulty
      5
      Tags
      # Submissions
      10
      Accepted
      4
      Uploaded By