2878376_tle.cpp

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

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

int n;
int m, k;
int matrix[11][11];
struct node
{
	int mat[11][11];
};

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

	nn = mm;
	if(mm%2==0)
		nn/=2;
	while(mm%2==0)
		mm/=2;
	for(i = 3; mm!=1; i+=2)
	{
		if(mm%i==0)
			nn -= nn/i;
		while(mm%i==0)
			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)
		return muti(power(a,nn-1),a);
	else
		return power(muti(a,a),nn/2);
}

int main()
{
	int i, j, cas;
	int a, b, t, d;
	__int64 ans, e;
	node tmp, tt;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d%d",&n,&m,&k);
		for(i = 0; i < m; i++)
			for(j = 0; j < m; j++)
				tmp.mat[i][j] = matrix[i][j] = 1;
		for(i = 0; i < k; i++)
		{
			scanf("%d%d",&a,&b);
			matrix[a-1][b-1] = tmp.mat[a-1][b-1] = 0;
		}
		t = (int)sqrt(n);
		e = n;
		e *= 9973;
		ans = 0;
		for(d = 1; d <= t; d++)
		{
			if(n/d*d==n)
			{
				tt = tmp;
				ans += fai(d)*tr(power(tt,n/d));
				ans %= e;
				if(d!=n/d)
				{
					tt = tmp;
					ans += fai(n/d)*tr(power(tt,d));
					ans %= e;
				}
			}
		}
		printf("%I64d\n",(ans/n)%9973);
	}
	return 0;
}