【poj 2407】Relatives（数论--欧拉函数 模版题）
2024-10-17 09:04:41
题意就是求10^9以内的正整数的欧拉函数（Φ(n)表示<=n的与n互质的正整数个数）。
解法：用欧拉筛和欧拉函数的一些性质：
1.若p是质数，Φ(p)=p-1；
2.欧拉函数是积性函数，即若a,b互质，则Φ(ab)=Φ(a)*Φ(b)；
3.若a,b不互质，则Φ(ab)=Φ(a)*b。
若 n≤10^6，可以通过欧拉筛用数组预处理得出；若不是，再分解质因数，利用Φ(n)=n*(1-1/p1)*(1-1/p2)*...*(1-1/pk) {除去各质因数的 n 以内的倍数}求出。
P.S. n 不是10^6以内分解质因数并求解时要注意啊，我WA了7次！ %>_<%
P.P.S. 这题数据弱，不用欧拉筛更快......不写mn_prim，而用标记数组也是可以的。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<cmath>
5 #include<iostream>
6 using namespace std;
7 #define N (int)1e9
8 #define M (int)1e6
9 typedef long long LL;
10
11 int phi[M+10],prim[M+10],mn_prim[M+10];
12 int pr=0;
13
14 void get_prime()
15 {
16 memset(mn_prim,0,sizeof(mn_prim));
17 for (int i=2;i<=M;i++)
18 {
19 if (!mn_prim[i])
20 {
21 prim[++pr]=i;
22 phi[i]=i-1;
23 }
24 for (int j=1;j<=pr,i*prim[j]<=M;j++)
25 {
26 mn_prim[i*prim[j]]=prim[j];
27 if (i%prim[j]!=0)
28 phi[i*prim[j]]=phi[i]*phi[prim[j]];
29 else
30 {
31 phi[i*prim[j]]=phi[i]*prim[j];
32 break;
33 }
34 }
35 }
36 }
37 int main()
38 {
39 get_prime();
40 int n;
41 while (1)
42 {
43 scanf("%d",&n);
44 if (!n) break;
45 if (n<=M-10) printf("%d\n",phi[n]);
46 else
47 {
48 int cnt=n,t=n;
49 for (int i=2;i<=t;i++)//t
50 {
51 if (t%i==0)
52 {
53 cnt-=cnt/i;// cnt*(1-1/i);
54 while (t%i==0) t/=i;
55 }
56 if (t==1) break;
57 }
58 printf("%d\n",cnt);
59 }
60 }
61 return 0;
62 }
最新文章
- WPF 开发 WebBrowser
- H5案例分享：html5移动开发细微之美
- Qt开发中的实用笔记二--中文转码问题和string转换问题：
- CURLcode curl_easy_setopt（原创）
- 简单Ztree的实现————不连接数据库版
- java8 引进lamda
- 使用ssh-keygen设置ssh无密码登录
- C语言 串 顺序结构 实现
- WeisEditor 3.2.1B 使用说明 [源码下载]
- ExtGrid
- 第4章 管道与FIFO
- MVC 音乐商店 第 9 部分： 注册和结帐
- C#控件TabControl隐藏page
- Nginx反向代理配置文件
- asp.net core 2.0集成signalr
- Layx——网页弹窗最佳选择.
- Android版本分布数据源
- MySQL数据库有哪些安全相关的参数需要修改？
- IDEA 工具从Json自动生成JavaBean
- NPOI DataSet导出excel