【POJ 1286】Necklace of Beads

题目传送门:http://poj.org/problem?id=1286

polya的板题,其中置换的循环节先用一下程序算,之后再写程序

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100;

int to[MAXN],tag[MAXN],ty,delta,n;

inline int Get_M(){
	int ret = 0;
	for (int i=1,w;i<=n;i++) if (!tag[i]) {
		ret++; w = i;
		while (!tag[w]) tag[w] = 1, w = to[w];
	} return ret;
}

int main(){
	cin>>n>>delta>>ty;
	if (ty == 1) {
		for (int i=1;i<=n;i++) to[i] = i + delta;
		for (int i=1;i<=n;i++) if (to[i] > n) to[i] -= n;
	} else {
		for (int j=1,i=delta;j<=n;j++,i=++i>n?i-n:i) to[i] = n - i;
	} cout<<Get_M();
	return 0;
} 

主程序:

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int col = 3;

inline LL pow(int w, int t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret *= w;
		t >>= 1, w *= w; 
	}
	return ret;
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	for (int n=read();~n;n=read()) {
		if (n == 0) {cout<<0<<endl; continue;}
		else { 
			LL vout = 0; int t = n;
			for (int i=1;i<=n;i++) vout += pow(col,GCD(i,n));
			
			if (n & 1) {for (int i=1;i<=n;i++) vout += pow(col,n/2+1); t += n;} 
			else {
				for (int i=1;i*2<=n;i++) vout += pow(col,n/2+1); t += n/2;
				for (int i=1;i*2<=n;i++) vout += pow(col,n/2); t += n/2;
			}
			
			vout /= t;
			printf("%lld\n",vout);
		}
	} 
	return 0;
}

2 thoughts to “【POJ 1286】Necklace of Beads”

Leave a Reply

Your email address will not be published. Required fields are marked *