马特维尔兔窟

以前写容斥原理时,用的都是dfs~

今天突然想到...格雷碼,每次只改变一位,貌似可以用来写容斥原理;

然后就写了一个

const int BT[]={0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8,31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9};
#define BIT4CHG(i) BT[(unsigned int)((((i)+1)&~(i))*0x077CB531U)>>27]

其中的BIT4CHG,就是告诉你第i个格雷碼变成第i+1个时(i从0开始算),改变的是第几位~之所以可读性这么差是因为使用了这里的技巧.

这就避免了dfs递归了......

其实,这个效率确实提高不了多少~而且写起来没那么好看~

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define swap(a,b) do{a=a^b;b=a^b;a=a^b;}while(0)
typedef long long LL;
LL gcd(LL a,LL b)
{
	while(b){swap(a,b);b=b%a;}
	return a>0?a:-a;
}
LL mod_mult(LL a,LL b,LL mo)//ret:a*b%mo
{
	LL ret;
	a%=mo;
	for(ret=0;b;a=(a<<1)%mo,b>>=1)
		if(b&1)
			ret=(ret+a)%mo;
	return ret;
}
LL mod_exp(LL a,LL b,LL mo)//ret:a^b%mo
{
	LL ret=1,temp=a%mo;
	for(;b;b>>=1,temp=mod_mult(temp,temp,mo))
		if(b&1)
			ret=mod_mult(ret,temp,mo);
	return ret;
}
LL pollard_rho(LL n,int c)
{
	LL x,y,d,i=1,k=2;
	x=rand()%(n-1)+1;
	y=x;
	while(1)
	{
		i++;
		x=(mod_mult(x,x,n)+c)%n;
		d=gcd(y-x,n);
		if(d>1&&d<n)return d;
		if(x==y)return n;
		if(i==k)y=x,k<<=1;
		//if(k>1<<11)return n;
	}
}

int miller_rabin(LL n,int time)
{
	if (n==2||n==3||n==5||n==7)return 1;
	if (n<2||!(n&1))return 0;
	int i,j,t=0;
	LL a,x,y,u=n-1;
	while((u&1)==0) t++,u>>=1;
	for(i=0;i<time;i++)
	{
		a=rand()%(n-1)+1;
		x=mod_exp(a,u,n);
		for(j=0;j<t;j++)
		{
			y=mod_mult(x,x,n);
			if (y==1&&x!=1&&x!=n-1)
				return 0;
			x=y;
		}
		if (x!=1)
			return 0;
	}
	return 1;
}
LL min;
void fuck(LL i)
{
	LL x;
	if(miller_rabin(i,8)){if(i<min)min=i;/*printf(" %lld ",i);*/return;}
	do{x=pollard_rho(i,rand()%15+2);}while((x==1||x==i));
	fuck(x);
	fuck(i/x);
}
int main()
{
	LL i;int t;
	scanf("%d",&t);
	while(t--){
	scanf("%lld",&i);
	min=i;
	fuck(i);
	if(i!=min)printf("%lld\n",min);
	else printf("Prime\n");}
	return 0;
}

//Z2上高斯消元求秩,用位压缩储存
int rank(long long a[],int n)
{
	int i,j;
	for(i=0;i<63;i++)
	{
		int mask=1<<i;
		for(j=i;j<n;j++)if(a[j]&mask){swap(a[i],a[j]);break;}
		for(j++;j<n;j++)if(a[j]&mask)a[j]^=a[i];
	}
	for(i=j=0;i<n;i++)if(a[i])j++;
	return j;
}

貌似 dhclient-4.2.0-21.P2.fc14-x86_64 默认的 dhclinet.conf 在 /etc/dhcp/里，要手动创建

曼哈顿距离是什么-->http://zh.wikipedia.org/zh-hant/%E6%9B%BC%E5%93%88%E9%A0%93%E8%B7%9D%E9%9B%A2

经过冗长的推导会发现这个等式成立

d=|x1-x2|+|y1-y2|

=max{(x1+x2)-(y1+y2) , (x1-x2)-(y1-y2) , (-x1+x2)-(-y1+y2) , (-x1-x2)-(-y1-y2)}

计算两点间的曼哈顿距离，这式子完全没用，但是，给定N个点，求他们的最大哈密顿点对是，就很好用了。

朴素方法算复杂度是O(N²)，而利用这个式子复杂度为O(N*2^k)，k是维度，上面写的是2维的情况，高维情况类比可得。

Description

Input

Output

Sample Input

0 0 4 0 0 1 
7 5 1 0 0 0 
0 0 0 0 0 0 

Sample Output

2 
1 

#include	<stdlib.h>
#include	<stdio.h>
#include	<string.h>
#define dill do{if(s[2]<0)s[1]-=4*(-s[2]);if(s[1]<0)s[1]=0;if(s[2]<0)s[2]=0;}while(0)
	int
main ( int argc, char *argv[] )
{
	int s[7],i,sum=0,t[3][2]={{1,5},{3,6},{5,7}};
	for(;;)
	{
		sum=0;
		for(i=1;i<=6;i++){scanf("%d",&s[i]);sum+=s[i];}
		if(sum==0)break;
		sum=0;
		sum+=s[6]+s[5]+s[4]+s[3]/4;
		s[1]-=11*s[5];
		s[2]-=5*s[4];
		dill;
		s[3]%=4;
		if(s[3]){
			s[2]-=t[3-s[3]][0];
			s[1]-=t[3-s[3]][1];
			sum++;
			dill;
		}
		sum+=s[2]/9;
		s[2]%=9;
		if(s[2]){
			s[1]-=36-s[2]*4;
			sum++;
		}
		if(s[1]>0)sum+=s[1]/36+(s[1]%36>0?1:0);
		printf("%d\n",sum);
	}
	return EXIT_SUCCESS;
}

kruskal：
输入：边集E

for each <u,v> in E

        //用并查集实现

        if u.root != v.root //u v 不在同一集合（不会产生回路）

             union(u,v)//加入变<u,v>

合并同时记录边数，由于n个点的生成树只有n-1条边，一旦加够了，就停

//并查集的实现

int root[MAXN];//记录每个节点的根节点

void init(int x)//初始化
{
     for(int i=0;i<x;i++)root[i]=i;//每个节点开始时独立
}

int getroot(int x)//取出根节点，顺便压缩路径
{
    if(x!=root[x])root[x]=getroot(root[x]);
    return root[x];
}

inline int unionset(int x1,int x2)//合并俩集合
{
    int a=getroot(x1),b=getroot(x2);
    root[a]=b;
}