http://acm.pku.edu.cn/JudgeOnline/problem?id=2480 這道題改了兩天，里面用到了整數(shù)因子分解，篩選素?cái)?shù)，求歐拉函數(shù)，
以下是和partychen的聊天記錄，既然他把那么難敲得證明都
敲出來(lái)了，那我就只接捻好了HOHO~~
主要公式：
sima(N/pi)*pi另外這個(gè)公式是可積的陳俊奎 10:13:35
m的約數(shù)為x1,x2,x3...xp
陳俊奎 10:13:48
n的約數(shù)為y1,y2,y3....yp
陳俊奎 10:14:05
那么有g(shù)cd(xi,yi)=1
陳俊奎 10:15:14
那么m*n的任意約數(shù)T，有唯一分解T=xi*yj
陳俊奎 10:16:47
T*E(m*n/T)=xi*yi*E(m/xi* n/ yj)=xi*E(m/xi)*yj*E(n / yj)
陳俊奎 10:18:09
f(m*n)=sima(xi*E(m/xi)*yj*E(n / yj))=(sima(xi*E(m/xi))*(sima(yj*E(n/ yj)))=f(m)*f(n)
陳俊奎 10:19:31
f(12)=f(2^2)*f(3)
陳俊奎 10:20:00
f(3)=1*E(3)+3*E(1)=2+3=5
陳俊奎 10:21:14
f(2^2)=1*E(2^2)+2*E(2)+4*E(1)=(2-1)*2^(2-1)+2*(2-1)+4*1
陳俊奎 10:21:25
=2+2+4=8
1
#include<iostream>
2using namespace std;
3#define Max_N 50000
4#define Max_P 5200
5#define __int64 _int64
6int Prime[Max_N];//對(duì)素?cái)?shù)的標(biāo)記
7int P_div[Max_P];//存儲(chǔ)素?cái)?shù)約數(shù)
8int P_mi[Max_P];//存儲(chǔ)素?cái)?shù)約數(shù)的冪
9void init()//篩選素?cái)?shù)
10{
11 _int64 i,j;
12 for(i=2;i<Max_N;i++)
13 if(!Prime[i])
14 for(j=2;j*i<Max_N;j++)Prime[j*i]=1;
15}
16_int64 phi(int p,int e)//歐拉
17{
18 if(e==0||p==1)return 1;
19 if(e==1)return p-1;
20 _int64 i;
21 _int64 result=1;
22 for(i=1;i<e;i++)
23 result*=p;
24 result*=(p-1);
25 return result;
26}
27int get(int i,int e)
28{
29 int j;
30 int r=1;
31 for(j=e;j<P_mi[i];j++)
32 r*=P_div[i];
33 return r;
34}
35int factorization(int n)//整數(shù)因子分解
36{
37 int i,j=0;
38 for(i=2;i<Max_N&&n>1;i++)
39 if(!Prime[i]&&n%i==0){
40 P_div[j]=i;
41 while(n%i==0){
42 ++P_mi[j];
43 n/=i;}
44 j++;}
45 if(i>=Max_N||!j){//好重要的疏漏！！！大素?cái)?shù)因子沒(méi)有存入P_div中
46 P_div[j]=n;//吸取教訓(xùn)的地方！！
47 P_mi[j++]=1;}
48 return j;
49}
50int main()
51{
52 //freopen("1.in","r",stdin);
53 //freopen("1.ans","w",stdout);
54 int N;
55 int i,j,t,h,tmp1;
56 _int64 tmp2;
57 _int64 result,p;
58 memset(Prime,0,sizeof(Prime));
59 init();
60 while(scanf("%d",&N)!=EOF){//
61 result=1;
62 memset(P_div,0,sizeof(P_div));
63 memset(P_mi,0,sizeof(P_mi));
64 t=factorization(N);
65 for(i=0;i<t;i++){
66 for(p=0,j=0,h=1;j<=P_mi[i];j++){
67 tmp1=get(i,j);
68 tmp2=phi(P_div[i],j);
69 p+=tmp2*tmp1;}
70 result*=p;}
71 printf("%I64d\n",result);
72 }
73 return 0;
74}
posted on 2008-03-01 20:19
zoyi 閱讀(377)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm