HDOJ 1817 Necklace of Beads

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1817

此题就是一个弱化版本的HDOJ 3923 Invoker，区别在于颜色数都是定死的(所以说是弱化版的)，要是不会的同学可以去看看小编的另一篇博客。

#include <stdio.h>
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
long long Pow(long long a,int b)
{long long c=1;while(b){if(b&1) c*=a;a*=a;b>>=1;}return c;
}
long long flip(int n)
{long long ans;if(n&1)return Pow(3LL,n/2+1)*n;else{ans=Pow(3LL,n>>1)*(n>>1);ans+=Pow(3LL,n/2+1)*(n>>1);return ans;}
}
long long spin(int n)
{int i;long long ans=Pow(3LL,n);for(i=1;i<n;i++)ans+=Pow(3LL,gcd(n,i));return ans;
}
int main(void)
{int n;long long ans;while(scanf("%d",&n)==1&&n!=-1){if(n==0){puts("0");continue;}if(n==1){puts("3");continue;}ans=flip(n);ans+=spin(n);printf("%I64d\n",ans/(n<<1));}return 0;
}