20150131
20150201

POJ2154 Color

laekov posted @ 2015年2月01日 23:18 in 未分类 with tags poj burnside math , 688 阅读

首先是burnside,对于旋转x下都要当作一个置换,所以总共有n个。然后第i个的不动点数量等于ngcd(n,i),然后统计一下个数是phi(gcd(n,i))个。

 

然后发现要用奇奇怪怪的东西来求phi。我用的方法是分解质因数然后DFS,跑得飞快。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define _l (long long int)

const int maxn = 50009;

int n, mod;
int tp, pn[maxn], phi[maxn];
bool pr[maxn];

void pre() {
	memset(pr, 0, sizeof(pr));
	tp = 0;
	phi[1] = 1;
	for (int i = 2; i < maxn; ++ i) {
		if (!pr[i]) {
			pn[tp ++] = i;
			phi[i] = i - 1;
		}
		for (int j = 0; j < tp && i * pn[j] < maxn; ++ j) {
			pr[i * pn[j]] = 1;
			if (i % pn[j] == 0) {
				phi[i * pn[j]] = phi[i] * pn[j];
				break;
			}
			else
				phi[i * pn[j]] = phi[i] * phi[pn[j]];
		}
	}
}

int modPow(int a, int x) {
	int s(1);
	for (a %= mod; x; x >>= 1, a = _l a * a % mod)
		if (x & 1)
			s = _l s * a % mod;
	return s;
}

int fv[maxn], fc[maxn], tv, ans;

void dfs(int p, int pf, int pv) {
	if (p == tv)
		ans = (ans + _l modPow(n, pv - 1) * pf) % mod;
	else {
		dfs(p + 1, pf, pv);
		pf *= fv[p] - 1;
		pv /= fv[p];
		dfs(p + 1, pf, pv);
		for (int i = 2; i <= fc[p]; ++ i) {
			pf *= fv[p];
			pv /= fv[p];
			dfs(p + 1, pf, pv);
		}
	}
}

int calc() {
	int x(n);
	tv = 0;
	for (int i = 0; i < tp && x > 1; ++ i)
		if (x % pn[i] == 0) {
			fv[tv] = pn[i];
			fc[tv] = 0;
			while (x % pn[i] == 0) {
				++ fc[tv];
				x /= pn[i];
			}
			++ tv;
		}
	if (x > 1) {
		fv[tv] = x;
		fc[tv] = 1;
		++ tv;
	}
	ans = 0;
	dfs(0, 1, n);
	return ans;
}

int main() {
	//freopen("in.txt", "r", stdin);
	int t;
	pre();
	scanf("%d", &t);
	while (t --) {
		scanf("%d%d", &n, &mod);
		if (mod == 1)
			puts("0");
		else
			printf("%d\n", calc());
	}
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter