jiry_2's Blog

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;
}