来源:http://poj.org/problem?id=1286
题意:用三种颜色着色一个长度为n的项链,问有多少种方法。。。
思路:继续裸的Ploya,水水更健康。。。被n=0坑了一次re,被long long坑了一次wa,,,
代码:
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
typedef long long ll;
int gcd(int a,int b){
if(b == 0)
return a;
return gcd(b,a%b);
}
ll mi(int x){
ll s = 1;
for(int i = 1;i <= x;++i)
s *= 3;
return s;
}
int main(){
int n;
while(scanf("%d",&n) != EOF){
if(n == -1)
break;
if(n == 0){
printf("0\n");
continue;
}
ll sum = 0;
for(int i = 1;i <= n;++i){
int x = gcd(n,i);
sum += mi(x);
}
if(n % 2)
sum += ( n * mi( (n-1)/2 + 1 ) );
else
sum += ( n/2 * mi( n/2 ) + n/2 * mi( n/2 + 1 ));
printf("%lld\n",sum / (2*n));
}
return 0;
}
分享到:
相关推荐
北大POJ1129-Channel Allocation【四色定理】 解题报告+AC代码
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
poj 2771 Guardian of Decency.md
北大POJ1006-Biorhythms【中国剩余定理】 解题报告+AC代码
poj 3174 Alignment of the Planets.md
poj 2903 Joy of Mobile Routing.md
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2109-Power of Cryptography 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
北大POJ2739-Sum of Consecutive Prime Numbers 解题报告+AC代码
北大POJ3083-Children of the Candy Corn 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj 3495 Bitwise XOR of Arithmetic Progression.md
北大POJ1159-Palindrome 解题报告+AC代码
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友