4
5
2014
1

【数学】我要学数学

ZJOI2014day1居然有两道数学题,再加上WC的经历,看来这个世界不会数学是混不成OI了,于是现在开始学数学吧。。。

膜拜了策神的博客,感触颇多,也学到了很多,做了几道题。

【BZOJ1101】【POI2007】ZAP 用莫比乌斯函数带进去搞搞就好了。

【BZOJ1693】jzptab 方法和上面差不多,莫比乌斯函数带进去然后再代换求和指标,把问题转化为求一个Dirichlet卷积。然后就线性筛做就可以了。

【BZOJ3309】方法同上,最后化出来一个感觉很靠谱的式子,但是要求f和µ的Dirichlet卷积,可以发现当为k个指数相同质数相乘时卷积为(-1)k+1,否则为0。的开始我只会O(nloglogn)的算法,显然TLE,后来一想只要先筛莫比乌斯函数,然后对于每个非0项自乘就可以了,非常简单而且复杂度O(n)

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long s[10000010],prime[10000000],pd[10000010],len,n,m;
void makeit()
{
	long long n=10000000;
	memset(s,0x00,sizeof s);
	memset(pd,0x00,sizeof pd);
	for (long long i=2;i<=n;i++)
	{
		if (!pd[i]) 
		{
			len++; prime[len]=i; s[i]=1;
		}
		for (long long j=1;j<=len;j++)
		{
			if (prime[j]*i>n) break;
			pd[prime[j]*i]=1;
			if (i%prime[j]==0)
			{
				s[i*prime[j]]=0; break;
			} else s[i*prime[j]]=-s[i];
		}
	}
	for (long long i=2;i<=int(sqrt(n));i++)
		if (s[i]!=0)
			for (long long j=i;j<=n;j=j*i)
				s[j]=s[i];
	for (long long i=2;i<=n;i++) s[i]+=s[i-1];
}
int main()
{
	int t; makeit();
	scanf("%d",&t);
	for (;t;t--)
	{
		scanf("%lld%lld",&n,&m);
		if (n>m) swap(n,m); long long tot=0,next; 
		for (long long i=1;i<=n;i=next+1)
		{
			next=min(n/(n/i),m/(m/i));
			tot+=(s[next]-s[i-1])*(m/i)*(n/i);
		}
		printf("%lld\n",tot);
	}
	return 0;
}

 

Category: 数学题 | Tags: | Read Count: 1802
Avatar_small
Emma 说:
2023年1月24日 01:12

Comment: It seems that understanding mathematics is a key factor to success in the world of Online Judge (OI). I recently read Ceshen's blog and it was incredibly eye-opening. I tried a few of the math problems such as BZOJ1101, POI2007 and BZOJ1693 which required using the Möbius function to solve. The real estate services Gray algorithm for BZOJ3309 was similar but required a Dirichlet convolution of f and µ. After some research, I figured out that a linear sieve was the best approach. It was an enlightening experience and I'm grateful to Ceshen's blog for introducing me to the world of mathematics.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com