随笔 - 87  文章 - 279  trackbacks - 0
<2007年11月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214292
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

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

FeedBack:
# re: 扩展的欧拉函数 pku1091 2007-09-18 09:41 nice
这个公式好牛,类比的好强  回复  更多评论
  
# re: 扩展的欧拉函数 pku1091[未登录] 2007-10-07 10:35 beyond
你好,常来你个Blog,故对你的网名很熟悉,近日在NUAA( Latin Stones 1110 )上看你做了一题欧拉定理得题,那题我没有i想法,能把递推公式还有代码发给我,供学习参考吗?非常感谢!我的邮箱是:beyondjjj@tom.com  回复  更多评论
  
# re: 扩展的欧拉函数 pku1091 2007-10-07 20:43 
@beyond
-_-这题不会,我那时候想dp结果发现不行。。。  回复  更多评论
  
# re: 扩展的欧拉函数 pku1091 2008-05-28 18:04 maik
你上面的讲解跟程序有出入哦...
上面应该是判断m是否为素数,且p应该是m的因子  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理