polya计数法

简单模板

?

void solve(int n,int c)
{
    int ans = 0;
    for (int i = 1; i <= n; i++) if (n % i == 0)
        {
            ans += fun(c, i) * euler(n / i);
        }
    if (n & 1) ans += n * fun(c, n / 2 + 1);
    else ans += n / 2 * (fun(c, n / 2) + fun(c, n / 2 + 1));
    cout << ans / (2 * n) << endl;
}

?

?

#include
  
   
#include
   
     using namespace std; int fun(int a,int x) { int ans=1; while(x) { if(x&1) ans=ans*a; a=a*a; x>>=1; } return ans; } int euler(int n){ int res=n,a=n; for(int i=2;i*i<=a;i++){ if(a%i==0){ res=res/i*(i-1); while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } void solve(int n,int c) { int ans = 0; for (int i = 1; i <= n; i++) if (n % i == 0) { ans += fun(c, i) * euler(n / i); } if (n & 1) ans += n * fun(c, n / 2 + 1); else ans += n / 2 * (fun(c, n / 2) + fun(c, n / 2 + 1)); cout << ans / (2 * n) << endl; } int main() { int n,c; while(~scanf("%d%d",&c,&n)&&n&&c) { solve(n,c); } return 0; } 
   
  

?