歐拉函數(shù)一般形式:
當(dāng) n 為素?cái)?shù)時(shí): phi(n) = n-1
當(dāng) n 為合數(shù)時(shí): phi(n) = n∏(1-1/p) 其中(p為n的素?cái)?shù)因子)
題目pku1091，要求我們求 x1..xn,m這樣的序列的個(gè)數(shù)，其中xi(1<=i<=n), 使 gcd(x1, ..,xn,m)=1;
我們按歐拉函數(shù)的形式猜想如下方程：
當(dāng) n 為素?cái)?shù)時(shí): phi(m,n) = m^n-1
當(dāng) n 為合數(shù)時(shí): phi(m,n) = m^n∏(1-1/p^n) 其中(p為n的素?cái)?shù)因子)
不給出嚴(yán)格數(shù)學(xué)證明(不會(huì)-_-)，上兩式具體含義：
當(dāng) n為素?cái)?shù) phi(m,n) = m^n-1 顯然成立
當(dāng) n 為合數(shù)時(shí) 可以假象有一個(gè)m進(jìn)制n位的數(shù)，然后其中一位有m的約數(shù)p的概率為1/p, 則n位同時(shí)有p的約數(shù)的概率就為(1-1/p^n), 運(yùn)用乘法原理，可以得式 phi(m,n) = m^n∏(1-1/p^n)
code:
#include <iostream>
using namespace std;
typedef __int64 llong;
const llong MAXN = 110000;
llong tf[MAXN], su[MAXN], ns, num[MAXN], nn;
void init() {
llong i, j;
for (i=2; i<MAXN; i++) {
if (!tf[i]) {
su[ns++]=i;
for (j=i*i; j<MAXN; j+=i) tf[j]=1;
}
}
}
llong ppow(llong a, llong b) {
llong ret=a;
llong i;
for (i=1; i<b; i++) ret *= a;
return ret;
}
int main() {
llong n, m, i, p;
llong ans=0;
init();
while (scanf("%I64d%I64d", &n, &m)!=EOF) {
p=m; nn=0; ans=0;
for (i=0; i<ns; i++) {
if (p%su[i]==0) {
while (p%su[i]==0) p/=su[i];
num[nn++]=su[i];
}
if (p==1) break;
}
if (!nn) {
ans = ppow(m,n)-1;
} else {
ans = ppow(m,n);
for (i=0; i<nn; i++) {
ans = ans/ppow(num[i],n)*(ppow(num[i],n)-1);
}
}
printf("%I64d\n", ans);
}
return 0;
}posted on 2007-09-02 22:57
豪 閱讀(2509)
評(píng)論(4) 編輯 收藏 引用 所屬分類:
算法&ACM