A

当两个格子的距离是N的因子（非1）时两个格子颜色相同，求最后有多少个不同颜色的格子(n<=10¹²)

格子的个数就是N的因子的GCD。
首先肯定只有N的质因子有用。
然后如果N有多个质因子，因为ax+by=gcd(a,b)=1一定有解，所以最小跨越的距离就是1
否则如果只有一个质因子，显然就是这个质因子。
如果这是一个质数的话，那就是它自己。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long 
using namespace std;

ll n;

int main(){
	freopen("ceshi.in","r",stdin);
	scanf("%lld",&n);
	for(int i=2;i<=sqrt(n);i++) if (n%i==0){
		while (n%i==0) n/=i;
		if (n!=1) printf("1
");
		else printf("%d",i);
		return 0;
	}
	printf("%lld",n);
}

B

求一个完全图的MST，其中有m条边边权为1，其他边权为0.

奇奇怪怪的想法都蹦了出来（除了正解）。
首先随便加入一个点。
考虑我们想要找到边权为0的边。
因为当前生成树中的点以1的边权连向一些点，所以不妨给这些点记录一下被覆盖的次数。
如果有一个点的被覆盖次数小于当前的生成树中的点数，那么一定有一条0的边。
用一个堆维护一下被覆盖的次数。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;

int n,m,i,j,k,x,y,vis[maxn],ans,nm[maxn];
int em,e[maxn*2],nx[maxn*2],ls[maxn],tot;
struct node{
	int x,i;
	node(int _x=0,int _i=0){x=_x,i=_i;}
} d[maxn];
int operator<(node a,node b){return a.x<b.x||a.x==b.x&&a.i<b.i;}


void insert(int x,int y){
	em++; e[em]=y; nx[em]=ls[x]; ls[x]=em;
	em++; e[em]=x; nx[em]=ls[y]; ls[y]=em;
}

void down(int x){
	for(int y=x*2;y<=tot&&d[y]<d[x]||y+1<=tot&&d[y+1]<d[x];x=y,y=x*2){
		if (y+1<=tot&&d[y+1]<d[y]) y++;
		swap(d[x],d[y]);
		nm[d[x].i]=x,nm[d[y].i]=y;
	}
}

void up(int x){
	for(int y=x/2;y&&d[x]<d[y];x=y,y=x/2){
		swap(d[x],d[y]);
		nm[d[x].i]=x,nm[d[y].i]=y;
	}
	down(x);
}

void change(int x){
	d[x].x++;
	down(x);
}

void del(int x){
	swap(d[x],d[tot]),tot--;
	if (x<=tot) nm[d[x].i]=x,up(x);
}

void add(node p){
	++tot,nm[p.i]=tot,d[tot]=p;
	up(tot);
}

int main(){
	freopen("ceshi.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++) {
		scanf("%d%d",&x,&y);
		insert(x,y);
	}
	for(i=1;i<=n;i++) add(node(0,i));
	for(i=0;i<n;i++) {
		node tmp=d[1];
		if (tmp.x==i) ans++;
		x=tmp.i,vis[x]=1;
		for(j=ls[x];j;j=nx[j]) if (!vis[e[j]]) 	
			change(nm[e[j]]);
		del(1);
	}
	printf("%d",ans-1);
}

C

给K(K<=15)个序列，每一个有ni(ni<=5000)个a，求一种方案将每一个序列的一个元素移动到一个序列中，每个序列移进来一个，移出去一个，使得最后每一个序列的a的和相等。

为什么我觉得C比A和B都更简单呢？？（除了代码长了点以外）
暴力枚举起点哪一个移出去，因为所有a都是不同的，并且目标都是确定的，所以只用O(Klogn)扫一遍看看是不是一个环（用个map）。
因为可能是很多个互相独立的环，所以直接子集转移就好了。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#define mem(a) memset(a,0,sizeof(a))
#define maxk 16
#define maxn 5005
#define ll long long 
using namespace std;

int K,n[maxk],i,j,k,S,a[maxk][maxn],vis[maxk];
int f[1<<maxk],g[1<<maxk],g0[1<<maxk];
int p[1<<maxk][maxk],q[1<<maxk][maxk],pp[maxk],qq[maxk];
ll sum0,sum[maxk],need,res;
struct node{
	int x,y;
	node(int _x=0,int _y=0){x=_x,y=_y;}
};
map<int,node> s;

void read(int &x){
	x=0; char ch=getchar(); int tp=1;
	for(;ch!='-'&&(ch<'0'||ch>'9');ch=getchar());
	if (ch=='-') tp=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	x=x*tp;
}

int dg(int T,int i,int S){
	if (i>K){
		if (f[T]&&g[S^T]) {
			g0[S]=T,g[S]=1;
			return 1;
		}
		return 0;
	}
	if (dg(T,i+1,S)) return 1;
	if ((S&(1<<i-1))&&dg(T|(1<<i-1),i+1,S)) return 1;
	return 0;
}

int main(){
	freopen("ceshi.in","r",stdin);
	read(K);
	for(i=1;i<=K;i++){
		read(n[i]);
		for(j=1;j<=n[i];j++) {
			read(a[i][j]);
			sum[i]+=a[i][j],sum0+=a[i][j];
			s[a[i][j]]=node(i,j);
		}
	}
	if (sum0%K) {printf("No");return 0;} 
	need=sum0/K;
	for(int sti=1;sti<=K;sti++) {
		for(int st=1;st<=n[sti];st++) {
			mem(vis),mem(pp),mem(qq);
			res=need-(sum[sti]-a[sti][st]);
			vis[sti]=1,i=sti,pp[sti]=st,S=1<<sti-1;
			node now=s[res];
			while (now.x&&!vis[now.x]){
				vis[now.x]=1,pp[now.x]=now.y,qq[now.x]=i,S|=1<<now.x-1;
				res=need-(sum[now.x]-a[now.x][now.y]);
				i=now.x,now=s[res];
			}
			if (now.x==sti&&res==a[sti][st]&&!f[S]) {
				qq[sti]=i,f[S]=1;
				memcpy(p[S],pp,sizeof(pp));
				memcpy(q[S],qq,sizeof(qq));
			}
		}
	}
	memcpy(g,f,sizeof(f));
	for(S=1;S<1<<K;S++) if (!g[S])
		dg(0,1,S); else g0[S]=S;
	if (g[(1<<K)-1]) {
		printf("Yes
");
		mem(pp),mem(qq);
		S=(1<<K)-1;
		while (S) {
			int T=g0[S];
			for(i=1;i<=K;i++) if (T&(1<<i-1)) 
				pp[i]=p[T][i],qq[i]=q[T][i];
			S^=T;
		}
		for(i=1;i<=K;i++) printf("%d %d
",a[i][pp[i]],qq[i]);
	} else printf("No");
}