欧拉函数一般形式:
当 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
豪 阅读(2481)
评论(4) 编辑 收藏 引用 所属分类:
算法&ACM