2009 Putnam Competition B3

题目大意：

\(T(t\le10^5)\)次询问，每次询问\(n(n\le2\times10^6)\)以内的正整数构成的集合，有多少满足若\(a\in S,b\in S\)且\(2|(a+b)\)，则\(\frac{a+b}2\in S\)。

思路：

OEIS A124197

显然，取值区间\([1,n]\)和\([2,n+1]\)答案是相等的。

用\(f(n)\)表示\(n\)以内的合法集合的答案，考虑二阶差分\((f(n+1)-f(n))-(f(n)-f(n-1))\)的含义，就是强制包含\(1\)和\(n+1\)时合法集合数。

线性筛出每个数奇约数的个数\(g_i\)，作二维前缀和\(h_i\)，然后答案就是\(h_{n-1}+n+1\)。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int N=2e6+1;

bool vis[N];

int64 f[N];

int p[N],q[N];

inline void sieve() {

	std::fill(&f[1],&f[N],1);

	for(register int i=2;i<N;i++) {

		if(!vis[i]) {

			q[i]=1;

			f[i]=2;

			p[++p[0]]=i;

		}

		for(register int j=1;j<=p[0]&&p[j]*i<N;j++) {

			vis[p[j]*i]=true;

			if(i%p[j]==0) {

				q[p[j]*i]=q[i]+1;

				f[p[j]*i]=f[i];

				f[p[j]*i]/=q[i]+1;

				f[p[j]*i]*=q[i]+2;

				break;

			} else {

				q[p[j]*i]=1;

				f[p[j]*i]=f[i]*2;

			}

		}

	}

}

int main() {

	sieve();

	for(register int i=1;i<N;i++) {

		if(i%2==0) f[i]=f[i>>1];

	}

	for(register int i=1;i<N;i++) f[i]+=f[i-1];

	for(register int i=1;i<N;i++) f[i]+=f[i-1];

	for(register int T=getint();T;T--) {

		const int n=getint();

		printf("%lld\n",f[n-1]+n+1);

	}

	return 0;

}

巴特西

2009 Putnam Competition B3

2009 Putnam Competition B3

题目大意：

思路：

源代码：

最新文章

热门文章