BZOJ3739: DZY loves math VIII
http://www.cnblogs.com/clrs97/p/5063707.html
#include<cstdio>
#include<iostream>
#define ll long long
char c;
inline void read(ll&a)
{
a=0;do c=getchar();while(c<'0'||c>'9');
while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();
}
const int Maxn=10000001;
int Prime[Maxn],tot;
ll S[Maxn];
int Mu[Maxn];
int Factor[Maxn];
bool Check[Maxn];
ll B,A;
ll ans;
int s[Maxn];
int Cache[101];
inline void Search(int Pos,int Cur)
{
if(Pos^(tot+1))Search(Pos+1,Cur),Search(Pos+1,Cur*Cache[Pos]);
else
s[Cur]+=A,B+=Mu[Cur]*s[Cur];
}
int main()
{
ll k;
ll T,n,m,i,j;
Mu[1]=1;
Factor[1]=1;
for(i=2;i<Maxn;i++)
{
if(!Check[i])
Factor[i]=Prime[++tot]=i,Mu[i]=-1;
for(j=1;j<=tot;j++)
{
k=i*Prime[j];
if(k>=Maxn)break;
Check[k]=1;
Factor[k]=Prime[j];
if(i%Prime[j])Mu[k]=-Mu[i];
else
{Mu[k]=0;break; }
}
}
//for(i=2;i<Maxn;i++)Mu[i]+=Mu[i-1];
for(i=1;i<Maxn;i++)
{
S[i]+=S[i-1];
if(A=Mu[i])
{
for(B=tot=0,j=i;j^1;j/=Factor[j])Cache[++tot]=Factor[j];
Search(1,1);
S[i]+=B*Mu[i];
}
}
read(T);
while(T--)
{
read(n);
printf("%lld
",S[n]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.