HDU 4834 JZP Set 2014 년 바 이 두 스타 프로 그래 밍 대회 - 1 차 전 (2 차 전) 수학
우 리 는 하나의 JZP Set 에서 3 개의 a, b, c 를 연속 으로 고려 하여 그들의 간격 을 고려 하여 d1 = b - a, d2 = c - b 를 기록 합 니 다. 만약 d1 또는 d2 가 짝수 라면 해당 하 는 두 수의 평균 수 는 이 집합 에 없 으 며 이 집합 은 JZP Set 이 아 닙 니 다.d1 과 d2 가 모두 홀수 라면 b! =(a + c) / 2, 그러면 a, c 두 항목 의 평균 수도 이 집합 안에 있 지 않 고 이 집합 도 JZP Set 이 아니다.그래서 JZP Set 안의 수 는 반드시 기수 가 공차 인 등차 수열 을 구성한다.
어떻게 계산 하 는 지 를 고려 하면 분명히 공 집 은 하나 이 고 단원 소 집 은 n 개 이다. 그러면 공차 가 1 인 등차 수열 은 (n - 1) + (n - 2) + (n - 3) +.
f (i) 를 i 로 하 는 기약수 개 수 를 기록 하면 얻 을 수 있 습 니 다. 숫자 p 의 상기 식 에서 f (p) 회 를 빼 었 습 니 다.s1 (i) 은 f (i) 의 접두사 와 s2 (i) 는 f (i) * i 의 접두사 와 n 을 기록 합 니 다. 그러면 우 리 는 n 이 상기 식 에 s1 (n - 1) + 1 회 추가 되 고 뺀 수의 합 계 는 s2 (n - 1) 입 니 다.
선형 체 법 으로 f (i) 를 계산 하면 O (n) 의 예비 처리 + O (1) 질문 을 할 수 있 습 니 다.
//HDU4834
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int MAXN=10000010;
bool nprime[MAXN];
int prime[750000],tot,dnum[MAXN],tms[MAXN],tms2[MAXN];
int s1[MAXN];
long long s2[MAXN];
int n,m;
long long ans;
void getPrime(int n)
{
for(int i=2;i<=n;i++)
{
if(!nprime[i]) {prime[++tot]=i,dnum[i]=2,tms[i]=1;}
for(int j=1;(j<=tot)&&(i*prime[j]<=n);j++)
{
nprime[i*prime[j]]=true;
if(i%prime[j]==0)
{
dnum[i*prime[j]]=dnum[i]/(tms[i]+1)*(tms[i]+2);
tms[i*prime[j]]=tms[i]+1;
break;
}
dnum[i*prime[j]]=dnum[i]*dnum[prime[j]];
tms[i*prime[j]]=1;
}
}
}
int main()
{
getPrime(10000000);
tms2[1]=0,tms2[2]=1,dnum[1]=1;
for(int i=3;i<=10000000;i++) if(!(i&1)) tms2[i]=tms2[i>>1]+1;
for(int i=1;i<=10000000;i++)
dnum[i]/=tms2[i]+1,s1[i]=s1[i-1]+(long long)dnum[i],s2[i]=s2[i-1]+(long long)i*dnum[i];
scanf("%d",&m);
for(int cas=1;cas<=m;cas++)
{
scanf("%d",&n);
ans=n+1+(long long)s1[n-1]*n-s2[n-1];
printf("Case #%d:
",cas);
printf("%I64d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.