题目

分析

因为\((-1)^2=1\)，

所以我们只用看\(\sum_{j=1}^md(i·j)\)的值模2的值就可以了。

易证，一个数x，只有当x是完全平方数时，d(x)才为奇数，否则为偶数。

那么设\(i=p*q^2\)，p不包含任何平方因子，

要使\(i·j\)为完全平方数，则\(j=p*k^2\),

因为\(j<=m\)

所以j就有\(\sqrt{\dfrac{m}{p}}\)。

因此我们可以求出每个i对应的p来算出答案。

但对于每个i都求出p的话，时间复杂度为\(O(n\sqrt{n})\)

发现\(i=p*q^2\)，当p固定时，q有很多种方案，

而\(\sqrt{\dfrac{m}{p}}\)也是固定的，

那么如果有一个i，p=i，那么

把这直接把所以是这个p的情况全部加入答案，

跳过并且这些所有的\(这个p*q^2\)。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=10000005;

using namespace std;

long long zs[300000],n,m,ans;

bool bz[N];

int main()

{

	memset(bz,true,sizeof(bz));

	scanf("%lld%lld",&n,&m);

	for(long long i=1;i<=n;i++)

	{

		if(!bz[i])

			continue;

		long long q=sqrt(n/i);

		long long k=sqrt(m/i);

		if(k%2)

			ans-=q;

		else

			ans+=q;

		for(int j=1;j<=q;j++)

			bz[i*j*j]=false;

	}

	printf("%lld",ans);

}

巴特西

【NOIP2016提高A组模拟9.15】Math

题目

分析

最新文章

热门文章