?

hdu2824 快速求歐拉函數

標簽：?integeroutputeachlessinput百度 2012-04-02 00:50?3499人閱讀?評論(0)?收藏?舉報 ?分類： 數論（7）?

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

目錄(?)[+]

歐拉函數的定義可以自己百度 phi(n)=n*(1-1/p1)*(1-1/p2)*...(1-1/pn)

主要是涉及到求很多個歐拉函數時的求法,這種題一般都是先初始化,

其中,在求素因子的時候處理的很巧妙,當phi[i]==i時,i就是素因子(可以拿起筆在草稿上畫一下就明白了),這個時候j+=i, 則j有素因子i,認真思考!

之前做過一道題,是求一個數的所以因子之和,也是類似的做法:

Problem Description

The hardest problem may not be the real hardest problem.
??Given a natural number n (1 <= n <= 500000), please output the summation of all its proper divisors. Definition: A proper divisor of a natural number is the divisor that is strictly less than the number. e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

Sample Input

3
2
10
20

Sample Output

1
8
22

關鍵代碼如下:

[cpp]?view plaincopy

1. void?init()??
2. {??
3. ?int?i,?j;??
4. ?memset(a,?0,?sizeof(a));??
5. ?for?(i?=?1;?i?<?500001;?i++)??
6. ??for?(j?=?i?+?i;?j?<?500001;?j?+=?i)??
7. ???a[j]?+=?i;??//a[j]表示j的所有因子之和,不包括本身??
8. }??

歐拉定理

早就看到了防止忘記先碼上

這個題首先我們要會歐拉定理

a?b % p = a?(b % phi(p)) % p

但是這個有一個前提，a和p必須互質，如果不互質的話是不對的。

但是有一個大神告訴我，不互質的情況下也有一個類似的定理。。
如果a和p不互質，且b大于等于phi(p)

a?b % p = a?(b % phi(p) + phi(p)) % p

hdu2824本題的代碼如下:

[cpp]?view plaincopy

1. #include?<iostream>??
2. #include?<cstdio>??
3. #include?<cmath>??
4. ??
5. using?namespace?std;??
6. ??
7. #define?bint?__int64??
8. #define?N?3000001??
9. ??
10. bint?phi[N];??
11. ??
12. void?init()??
13. {??
14. ????int?i,?j;??
15. ????for(i?=?1;?i?<?N;?i++)??
16. ????????phi[i]?=?i;??
17. ??
18. ????for(i?=?2;?i?<?N;?i++)??
19. ????????if(i?==?phi[i])?//此時i為素數??
20. ????????????for(j?=?i;?j?<?N;?j?+=?i)??//j累加i??
21. ????????????????phi[j]?=?(phi[j]?/?i)?*?(i?-?1);?//j有因子i,而且i是素數,正是歐拉函數??
22. }??
23. ??
24. int?main()??
25. {??
26. ????init();??
27. ????int?a,?b;??
28. ????while(scanf("%d%d",?&a,?&b)?!=?EOF)??
29. ????{??
30. ????????bint?ans?=?0;??
31. ????????for(int?i?=?a;?i?<=?b;?i++)??
32. ????????????ans?+=?phi[i];??
33. ????????printf("%I64d\n",?ans);??
34. ????}??
35. ????return?0;??
36. }??

總結

以上是生活随笔為你收集整理的快速求欧拉函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。