2879195_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <math.h>
#include <stdio.h>
#include <string.h>

int n;
int m, k;
struct node
{
	int mat[11][11];
};
node tmp, tt;
int no, num[1000], c[1000];
__int64 ans, e, nn;

int fai(int mm)
{
	int i, nn;

	nn = mm;
	if(mm/2*2==mm)
		nn/=2;
	while(mm/2*2==mm)
		mm/=2;
	for(i = 3; mm!=1; i+=2)
	{
		if(mm/i*i==mm)
			nn -= nn/i;
		while(mm/i*i==mm)
			mm/=i;
	}
	return nn;
}

int tr(node t)
{
	int i;
	int tt = 0;

	for(i = 0; i < m; i++)
		tt += t.mat[i][i];
	return tt;
}

node muti(node a,node b)
{
	node c;
	int i, j, k, tmp;

	for(i = 0; i < m; i++)
		for(k = 0; k < m; k++)
		{
			tmp = 0;
			for(j = 0; j < m; j++)
				tmp += a.mat[i][j]*b.mat[j][k];
			c.mat[i][k] = tmp;
		}
	return c;
}

node power(node a,int nn)
{
	if(nn==1)
		return a;
	if(nn/2*2!=nn)
		return muti(power(a,nn-1),a);
	else
		return power(muti(a,a),nn/2);
}

void dfs(int l,int p)
{
	int i, t;
	__int64 tt;

	if(l==no)
	{
		tt = fai(p)*tr(power(tmp,n/p));
		ans += tt;
		ans %= e;
		return ;
	}
	t = 1;
	for(i = 0; i <= num[l]; i++)
	{
		dfs(l+1,p*t);
		t *= c[l];
	}
}

int main()
{
	int i, j, cas;
	int a, b, q;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d%d",&n,&m,&k);
		if(n==1)
		{
			printf("%d\n",m);
			continue;
		}
		e = nn = n;
		e *= 9973;
		for(i = 0; i < m; i++)
			for(j = 0; j < m; j++)
				tmp.mat[i][j] = 1;
		for(i = 0; i < k; i++)
		{
			scanf("%d%d",&a,&b);
			tmp.mat[a-1][b-1] = tmp.mat[b-1][a-1] = 0;
		}
		no = 0;
		memset(num,0,sizeof(num));
		if (n%2==0)
		{
			c[no] = 2;
            while (n%2==0)
            {
				n /= 2;
                num[no]++;
			}
			no++;
		}
		q = (int)sqrt(n)+1;
        for (i = 3; i < q&&n!=1; i+=2)
		{
			if (n%i==0)
			{
				c[no] = i;
                while (n%i==0)
				{
					n /= i;
                    num[no]++;
				}
				q = (int)sqrt(n)+1;
                no++;
			}
		}
		if (n!=1)
        {
			c[no] = n;
            num[no]++;
            no++;
		}
		ans = 0;
		dfs(0,1);
		printf("%I64d\n",(ans/nn)%9973);
	}
	return 0;
}