歐拉函數一般形式:
當 n 為素數時: phi(n) = n-1
當 n 為合數時: phi(n) = n∏(1-1/p) 其中(p為n的素數因子)
題目pku1091，要求我們求 x1..xn,m這樣的序列的個數，其中xi(1<=i<=n), 使 gcd(x1, ..,xn,m)=1;
我們按歐拉函數的形式猜想如下方程：
當 n 為素數時: phi(m,n) = m^n-1
當 n 為合數時: phi(m,n) = m^n∏(1-1/p^n) 其中(p為n的素數因子)
不給出嚴格數學證明(不會-_-)，上兩式具體含義：
當 n為素數 phi(m,n) = m^n-1 顯然成立
當 n 為合數時 可以假象有一個m進制n位的數，然后其中一位有m的約數p的概率為1/p, 則n位同時有p的約數的概率就為(1-1/p^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
豪 閱讀(2518)
評論(4) 編輯 收藏 引用 所屬分類:
算法&ACM