程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2409Let it Bead

poj2409Let it Bead

編輯:C++入門知識

poj2409Let it Bead


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;
}

fun()函數是快速冪運算,enler是求歐拉數

 

 

#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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved