【POJ 2409】Let it Bead

题目传送门：http://poj.org/problem?id=2409
中文题面：http://blog.csdn.net/ww140142/article/details/47003643

同1286

#include<iostream>
#include<cstdio>
#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;
		printf("%lld\n",vout);
	} 
	return 0;
}