学步园

【题意】

用c种颜色染正s边形s个顶点有多少种不同的方案

【输入】

每行一个c、s

以两个0结束

【输出】

对于每组数据输出一个数表示有多少种不同的方案

polya定理经典模板

program poj2409;
var
  c,s,i,j,k:longint;
  ans:int64;

function gcd (a,b:int64):int64;
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=0 then exit(1);
  if b=1 then exit(a);
  i:=quick(a,b div 2);
  if b and 1 = 1 then exit(i*i*a)
                 else exit(i*i);
end;

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