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

先画成一个堆，然后就可以YY出递推式F[I]=F[I*2]*F[I*2+1]*C(C[I]-1,C[I*2])，C[I]是指以I为根的子树的节点个数，然后只需要把阶乘预处理出来，然后用逆元瞎搞搞就水过了。

program p2111;
	var
		c:array[0..2000000] of longint;
		x,num:array[0..2000000] of int64;
		i,j,n,q:longint;
	function quick(k1,k2:int64):int64;
		var
			i,j,tot:int64;
		begin
			i:=k2; j:=k1; tot:=1;
			while i<>0 do begin
				if i and 1=1 then
					tot:=tot*j mod q;
				i:=i shr 1; j:=j*j mod q;
			end;
			exit(tot);
		end;
	function dfs(k1:longint):int64;
		begin
			if num[c[k1]]<>-1 then exit(num[c[k1]]);
			if (c[k1]<=1) then begin
				num[c[k1]]:=1; exit(1);
			end;
			num[c[k1]]:=x[c[k1]-1]*quick(x[c[k1*2]],q-2) mod q*quick(x[c[k1]-1-c[k1*2]],q-2) mod q;
			num[c[k1]]:=num[c[k1]]*dfs(k1*2) mod q*dfs(k1*2+1) mod q;
			exit(num[c[k1]]);
		end;
	begin
		readln(n,q);
		fillchar(c,sizeof(c),0);
		fillchar(x,sizeof(x),0);
		for i:=n downto 2 do begin
			inc(c[i]);
			inc(c[i div 2],c[i]);
		end;
		inc(c[1]);
		fillchar(num,sizeof(num),-1);
		x[0]:=1; 
		for i:=1 to n do 
			x[i]:=x[i-1]*i mod q;
		writeln(dfs(1));
	end.

YY一下就可以得到最后的答案（因为有些并一起啊什么的全部都喜闻乐见消掉）为N*M^(K-1)-M*(M+1)/2*M^(K-2)*(K-1)，开始推了个式子貌似跪了，原因是中途要DIV个二好像有点问题，然后就索性重推了一遍。然后就A了，喜闻乐见。

program p3142;
	var
		n,m,k,p,i,j:int64;
	function quick(k1,k2:int64):int64;
		var
			i,j,k,tot:int64;
		begin
			k:=k1; j:=k2; tot:=1;
			while j<>0 do begin
				if j and 1<>0 then 
					tot:=tot*k mod p;
				j:=j shr 1; k:=k*k mod p;
			end;
			exit(tot);
		end;
	begin
		readln(n,k,m,p);
		dec(k);
		i:=quick(m,k-1); 
		writeln(int64(n mod p*m-m*(m+1) div 2 mod p*k+p*1000000000) mod p*i mod p);
	end.

瞎搞搞，用勾股定理的通式

program p1041;
	var
		len,tot,r,i,j:longint;
		x:array[1..10000,1..2] of longint;
	function find(k:longint):longint;
		var	
			i,j,a,b,num,c,d:longint;
			bo:boolean;
		begin
			num:=0;
			for i:=2 to trunc(sqrt(k)) do
				if sqr(trunc(sqrt(k-i*i)))=k-i*i then begin
					a:=trunc(sqrt(k-i*i));
					b:=i;
					if (a<=b) or (a=0) or (b=0) then continue;
					c:=2*a*b; d:=a*a-b*b;
					a:=c; b:=d;
					if a>b then begin j:=a; a:=b; b:=j; end;
					bo:=false;
					for j:=1 to len do begin
						if a/x[j,1]=b/x[j,2] then begin
							bo:=true; break;
						end;
					end;
					if bo=false then begin
						num:=num+2;
						inc(len);
						x[len,1]:=a; x[len,2]:=b;
					end;
				end;
			exit(num);
		end;
	begin
		readln(r);
		tot:=1; len:=0;
		for i:=1 to trunc(sqrt(r)) do
			if r mod i=0 then begin
				if i<>r div i then
					tot:=tot+find(i)+find(r div i)
				else 
					tot:=tot+find(i);
			end;
		tot:=tot*4;
		writeln(tot);
	end.