学步园

【题意】

正n边形n个顶点用3种颜色染色有多少种方法，对称旋转可得到的算同一种方法

【输入】

每行一个数表示顶点数

数据以-1结束

【输出】

对于每组数据，输出一个数表示方法数

polya计数模板题

    if n and 1 = 1 then ans:=n*quick(3,n div 2 + 1)
                   else ans:=(n div 2)*(quick(3,n div 2)+quick(3,n div 2+1));
    for i:=1 to n do
      ans:=ans+quick(3,gcd(i,n));
    ans:=ans div (2*n);

虽不明，但觉屌。

program poj1286;
var
  n,i,j,k:longint;
  ans:int64;

function gcd (a,b:longint):longint;
var
  i:longint;
begin
  while a mod b <> 0 do
    begin
      i:=a mod b;
      a:=b;
      b:=i;
    end;
  exit(b);
end;

function quick (a,b:int64):int64;
var
  i:int64;
begin
  if b=1 then exit(a);
  if b=0 then exit(1);
  i:=quick(a,b div 2);
  if b and 1 = 1 then exit(i*i*a)
                 else exit(i*i);
end;

begin
  repeat
    read(n);
    if n=-1 then exit;
    if n=0 then
      begin
        writeln(0);
        continue;
      end;
    if n and 1 = 1 then ans:=n*quick(3,n div 2 + 1)
                   else ans:=(n div 2)*(quick(3,n div 2)+quick(3,n div 2+1));
    for i:=1 to n do
      ans:=ans+quick(3,gcd(i,n));
    ans:=ans div (2*n);
    writeln(ans);
  until false;
end.