【POJ 2409】Let it Bead



#define LL long long
using namespace std;

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 col=read(),n=read();n && col;col=read(),n=read()) {
		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;
	return 0;

2 thoughts to “【POJ 2409】Let it Bead”

  1. naturally like your website but you have to test the spelling on several of your posts. Several of them are rife with spelling issues and I find it very troublesome to inform the truth nevertheless I will surely come again again.

Leave a Reply

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