西宁做网站君博示范,电子商务网站规划,设计案例网站,答题网站怎么做欧拉函数的作用#xff1a; 有[1,2.....n]这样一个集合#xff0c;f(n)这个集合中与n互质的元素的个数。欧拉函数描述了一些列与这个f(n)有关的一些性质#xff0c;如下#xff1a; 1、令p为一个素数#xff0c;n p ^ k#xff0c;则 f(n) p ^ k - p ^ (k-1) 2、令m 有[1,2.....n]这样一个集合f(n)这个集合中与n互质的元素的个数。欧拉函数描述了一些列与这个f(n)有关的一些性质如下 1、令p为一个素数n p ^ k则 f(n) p ^ k - p ^ (k-1) 2、令mn互质则 f(m*n) f(m) * f(n) 3、如果n为奇数则 f(2 * n) f(n) 下面给出一个例题的代码例题链接http://acm.hdu.edu.cn/showproblem.php?pid1286 1 #include cstdio2 #include cstring3 #include iostream4 #include algorithm5 #include vector6 #include string7 #include cmath8 using namespace std;9 const int maxn 32769;
10
11 int ans[maxn],prim[4000],flag_p[maxn];
12 /*
13 把1~maxn所有的素数打出来
14 */
15 int SolPrim()
16 {
17 memset(flag_p,0,sizeof(flag_p));
18 for(int i 2;i sqrt((double)maxn);i)
19 for(int j i * i;j maxn;j i)
20 flag_p[j] 1;
21 int f 0;
22 for(int i 2;i maxn;i)
23 if(!flag_p[i])
24 prim[f] i;
25 }
26 /*
27 打表把结果全部打出来
28 */
29 void PreSol()
30 {
31 int f SolPrim();
32 memset(ans,0,sizeof(ans));
33 for(int i 1;i 32768;i)
34 {
35 int temp 1,t i;
36 for(int j 0;prim[j] i;j)
37 {
38 int tt 0;
39 while(t % prim[j] 0)
40 {
41 t / prim[j];
42 tt;
43 }
44 if(tt) temp * (pow(prim[j],tt-1) * (prim[j] - 1));
45 }
46 ans[i] temp;
47 }
48 }
49
50 int main()
51 {
52 PreSol();
53 int T,n;
54 scanf(%d,T);
55 while(T--)
56 {
57 scanf(%d,n);
58 printf(%d\n,ans[n]);
59 }
60 return 0;
61 } View Code 转载于:https://www.cnblogs.com/xiaxiaosheng/p/4713977.html
