BZOJ 1005: [HNOI2008]明明的烦恼

prufer数列+高精度

http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html

详细的介绍可以看这篇blog

知道这个之后 只要计算prufer数列的个数就好了

首先将有度数限制的所有点数一下,这些点的度数-1就是在数列中出现的次数,这可以用含有重复元素的排列来解决。剩下来的位置可以用任意一个没有度数限制的点来填,乘法原理一下即可。

注意特判n=1和2的情况。

计算组合数的时候除法除单精度的数即可

#include <cstdio>
#include <algorithm>
using namespace std;
const int MOD=10,N=5010;
struct bigint{int a[N];
	void reset(){for(int i=0;i<N;i++) a[i]=0;a[0]=1;}
	void operator =(int x){
		reset();
		for(;x;x/=MOD,a[0]++) a[a[0]]=x%MOD;
		if(a[0]>1) a[0]--;
	}
	void print(){
		for(int i=a[0];i;i--) putchar(a[i]+'0');
	}
}ans;
int n,s[N],sum,sum2;
bigint operator *(bigint x,int y){
	for(int i=1;i<=x.a[0];i++) x.a[i]*=y;
	for(int i=1;i<x.a[0];i++) x.a[i+1]+=x.a[i]/MOD,x.a[i]%=MOD;
	for(int& i=x.a[0];x.a[i]>=MOD;i++) x.a[i+1]+=x.a[i]/MOD,x.a[i]%=MOD;
	return x;
}
bigint operator /(bigint x,int y){
	bigint z;int tmp=0;
	z=0;z.a[0]=x.a[0];
	for(int i=x.a[0];i;i--) z.a[i]=(tmp*MOD+x.a[i])/y,tmp=(tmp*MOD+x.a[i])%y;
	for(int &i=z.a[0];!z.a[i] && i;) 
		i--;
		if(!z.a[0]) z.a[0]++;
	return z;
}
int main(){
	scanf("%d",&n);
	if(n==1){
		scanf("%d",&s[1]);	
    		printf(s[1]?"0":"1");
       		return 0;
	}
	for(int i=1;i<=n;i++) {
		scanf("%d",&s[i]),s[i]>=1?sum+=s[i]-1:sum2++;
		if(!s[i]) {printf("0");return 0;}
	}
	if(sum>n-2) {printf("0");return 0;}
	ans=1;
	for(int i=n-2;i>=n-2-sum+1;i--) ans=ans*i;
	for(int i=1;i<=n;i++) if(s[i]>1) for(int j=1;j<=s[i]-1;j++) ans=ans/j;
	for(int i=1;i<=n-2-sum;i++) ans=ans*(sum2);
	ans.print();
	return 0;
}

BZOJ 2705: [SDOI2012]Longge的问题

考虑枚举gcd(i,n) =d 那么只要计数有多少个数和N的gcd是d

显然是phi(n/d)个

假设一个数可以表示成$p_{1}^{a1}+p_{2}^{a2}+...$,那么phi的结果就是 $(p_{1}-1)*p_{1}^{a1-1}*(p_{2}-1)*p_{2}^{a2-1}...$每次找到一个约数之后除干净就可以保证每次找到的都是质因数

计算phi是$\sqrt{n}$(枚举约数的复杂度) 枚举公约数$\sqrt{n}$ 时间复杂度$\sqrt{n}$

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
LL n,sq,ans;
LL phi(LL x){
	LL tmp=(LL)sqrt(x),ret=1;
	for(int i=2;i<=tmp;i++){
		if(x%i==0){
			ret*=i-1;x/=i;
			while(x%i==0) x/=i,ret*=i;
		}
	}
	if(x>1)ret=ret*(x-1);
	return ret;
}
int main(){
	scanf("%lld",&n);sq=(LL)sqrt(n);
	for(int i=1;i<=sq;i++){
		if(n%i==0) {
			ans+=i*phi(n/i);
			if(n/i!=i) ans+=(n/i*phi(i));
		}
	}
	printf("%lld",ans);
}

BZOJ 1257: [CQOI2007]余数之和sum

注意一个性质 k%n=k-k/(k/n)

于是可以化简成n*k-(k/i)*i  (1<=i<=min(n,k))

只要枚举k/i就可以了,令枚举的这个k/i为t

每一个满足 k/i=t的都在一个区间里

在这里说一下枚举的方法 这个方法复杂度是$\sqrt{n}$

for(int a=1;a<=min(n,k);a= k/(k/a)+1){
	//todo 两个a之间就是对应k/i= k/a 的区间
}

代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n,k,ans,t;
LL min(LL a,LL b){return a<b?a:b;}
int main(){
	// freopen("1257.in","r",stdin);freopen("1257.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for(t=1;t<=min(n,k);t=k/(k/t)+1){
		LL nxt=min(k/(k/t),n);
		nxt=min(nxt,k);
		ans+=(k/t)*(t+ nxt )*(nxt-t+1)/2;
	}
	ans=n*k-ans;
	printf("%lld",ans);
	return 0;
}
for(int a=1;a<=min(n,k);a= k/(k/a)+1){
	//todo
}

BZOJ 2190: [SDOI2008]仪仗队

有一个结论 一个点(x,y)到原点 经过gcd(x,y)个点 自己试一下就知道了 

于是这题只要求一下$(\sum_{i=1}^{n-1}phi(i)*2)+1$就好了 n的范围很小没必要用线性筛

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=40010;
int p[N],phi[N],n,vis[N],ans;
int main(){
	scanf("%d",&n);
	phi[1]=p[1]=1;
	for(int i=2;i<=n;i++) if(!vis[i]){
			p[i]=1;
			phi[i]=i-1;
			for(int j=2;j*i<=n;j++){
				if(!phi[i*j]) phi[i*j]=i*j;
				vis[i*j]=1;
				phi[i*j]=phi[i*j]*(i-1)/i;
			}
		}
	for(int i=1;i<n;i++) ans+=phi[i]*2;
	printf("%d",ans+1);
	return 0;
}

BZOJ2005 [NOI2010] 能量采集

这题就是求 $\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)*2-1)$

我们考虑枚举k使 gcd(i,j)=k

定义 g[k]表示以k为公约数的i,j有多少对,f[k]表示以k为最大公约数的i,j有多少对

首先我们想k是若干个数的公约数(非最大) 那么  g[k]=(n/k)*(m/k)

而以k为最大公约数的时候 要用g[k]减掉 f[2k],f[3k],f[4k]...于是 $f[k]=g[k]-\sum_{i=1}^{i*k<=min(n,m)}f[i*k]$

最后求一下和就好了

下面是代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
typedef long long LL;
LL f[N],n,m,mx,ans;
int main(){
	//freopen("2005.in","r",stdin);freopen("2005.out","w",stdout);
	scanf("%lld%lld",&n,&m);mx=min(n,m);
	for(int i=1;i<=mx;i++) f[i]=(n/i)*(m/i);
	for(int i=mx;i>=1;i--) 
		for(int j=2;j*i<=mx;j++) f[i]-=f[j*i];
	for(int i=1;i<=mx;i++) ans+=(i*2-1)*f[i];
	printf("%lld",ans);
	return 0;
}