2 solutions
-
0
#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
#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