我们有两种方法可以推导公式f(n,m)=m^n*∏(1-1/p^n)(p为m的素因子);
1.用容斥原理可以依次列出各项，最后化简得以上公式（化简的时候比较难看得出来）；
2.利用积性函数证明：
  (1).当m=p^k时，易知f(n,p^k)=p^k^n-p^(k-1)^n;
  (2).当m=a*b且(a,b)==1时，我们有Σa[i]*x1[i]+a*x1[n+1]=1和Σb[i]*x2[i]+b*x2[n+1]=1，
      那么由中国剩余定理x1[]，x2[]可以和x[]构成双射，从而有f(n,a*b)=f(n,a)*f(n,b);
  (3).由(1)(2)再根据素数唯一分解定理可得
      f(n,m)=∏(p[i]^(n*a[i])-p[i]^(n*(a[i]-1)))=m^n*∏(1-1/p[i]^n)。

容斥原理那种想法我也是看别人的，可是不管怎么样，就算以前的数据比较弱，知道公式后用脚趾头想都应该知道数据范围肯定超int64的啦-_-

• Re:可恶，谁说不超int64的-_- (34) 10074187 2009-08-07 16:14:28