首页 > > 程序设计 > C/C++ >

11.4

2018-06-17 21:38:20来源：未知阅读 ()

1637. 质质真真质质

★ 输入文件：zhione.in 输出文件：zhione.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

小质最近迷上了质数而不可自拔，噢，..my..，更有趣的是正整数a*b=gcd(a,b)*lcm(a,b)(最大公约数*最小公倍数)；后来小质又看到了互质的概念，便产生了兴趣，即最大公约数为1的两个自然数称为互质自然数，他发现用互质概念竟然能证明前面关于最大公约数的有趣算式，随即附上简单证明：

设x=gcd(a,b),y=lcm(a,b)

则a=m*x,b=n*x,m与n互质

故y=m*n*x

因此x*y=x*(m*n*x)=(m*x)*(n*x)=a*b

即a*b=gcd(a,b)*lcm(a,b)

总之，凡是带质字的东西，小质都感兴趣，因为他叫小质。

后来小质又发现了一个有趣概念叫既约真分数，虽然这个概念不带质字，但隐含质字。区间(0,1)中分子分母互质且不能再约分的真分数就叫既约真分数，经过日日夜夜日日的研究，小质发现既约真分数的个数是有一定规律的，比如分母小于等于N(N>1)的既约真分数个数：

f[2]=1——{ 1/2 }

f[3]=3——{ 1/3 , 1/2 , 2/3 }

f[4]=5——{ 1/4 , 1/3 , 1/2 , 2/3 , 3/4 }

…………………………………………………

小质的质之路还将一直质下去，现在小质想对前一段的质之智进行小结，他想编程求出不超过N(N>1)的正整数中质数的个数以及分母不超过N(N>1)的既约真分数个数。

【输入格式】

一个正整数N（N>1）;

【输出格式】

两行，一行一个正整数，分别表示题意中质数的个数和既约真分数个数。

【样例输入】

【样例输出】

3
9

【输出样例说明】

小于等于5的素数有2,3,5三个，故第一行输出3；

分母小于等于5的既约真分数有：

{ 1/5 , 1/4 , 1/3 , 2/5 , 1/2 , 3/5 , 2/3 , 3/4 , 4/5 }

共9个，故第二行输出9。

【数据规模】

40%的数据N<=1,0000

50%的数据N<=10,0000

60%的数据N<=100,0000

70%的数据N<=1000,0000

80%的数据N<=2000,0000

100%的数据N<=2900,0000

 1     #include<cstdio>
 2     #include<cstring>
 3     #include<iostream>
 4     #include<algorithm>
 5     #define maxn 29000005
 6     #define maxx 2000006
 7     using namespace std;
 8     void Emine(){
 9         freopen("zhione.in","r",stdin);
10         freopen("zhione.out","w",stdout);
11     }
12     int read(){
13         int x=0,f=1;char ch=getchar();
14         while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15         while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16         return x*f;
17     }
18     int n,ans1,f[maxn],pri[maxx],cnt;
19     long long ans2;
20     bool is_pri[maxn];
21     void getlist(int n){
22         memset(is_pri,true,sizeof(is_pri));
23         int k;f[1]=1;is_pri[1]=false;
24         for(int i=2;i<=n;i++){
25             if(is_pri[i]){pri[++cnt]=i;f[i]=i-1;}
26             for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
27                 is_pri[i*pri[j]]=false;
28                 if(i%pri[j]==0){
29                     f[i*pri[j]]=f[i]*pri[j];
30                     break;
31                 }
32                 else f[i*pri[j]]=f[i]*(pri[j]-1);
33             }
34         }
35     }
36     int main(){
37         Emine();
38         n=read();
39         getlist(n);
40         for(int i=2;i<=n;i++){
41             if(is_pri[i])ans1++;
42             ans2+=f[i];
43         }
44         printf("%d\n%lld",ans1,ans2);
45         return 0;
46     }

View Code

1638. 质质的询问

★☆ 输入文件：zhitwo.in 输出文件：zhitwo.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

质质最近又对欧拉函数产生了浓厚的兴趣。

欧拉函数φ(n)表示不超过n且与n互素的正整数的数目（其实等于仅对1而言，φ(1)=1，1被认为与任何数互素）

通式：

其中p1, p2……pn为x的所有质因数，x是不为0的整数。

注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4（即：1,5,7,11这四个数和12互素）

根据定义我们能在O(sqrt(n))时间复杂度内计算出n的欧拉函数值，但当我们要计算N个数的欧拉函数值时O(N*sqrt(n))已经不尽如人意了。

需要大咖们寻求更优秀的方法了。

欧拉函数的一些性质

欧拉函数是积性函数——若m,n互质，则

积性函数指对于所有互质的整数a和b有性质f(a*b)=f(a)*f(b)的数论函数。

当n为奇数时， ,证明与上述类似。

若n为质数则

设p是素数，若x%p==0，则E(x*p)=E(x)*p。若x%p!=0，则E(x*p)=E(x)*E(p)=E(x)*(p-1)。

现在，质质想请你帮忙计算数列1~N的某个区间[L，R]中的最大欧拉函数值对应的整数i的最小质因数（除自身外）；

若该区间中最大欧拉函数值存在多个，取其对应的i最小的那个；

如果i没有除本身外的最小质因数，那么输出其最小正约数；

【输入格式】

第一行一个正整数N，代表数列最大值；

第二行一个正整数Qn，代表质质的询问区间个数；

接下来Qn行，每行两个正整数Li，Ri，表达一个询问区间；

【输出格式】

输出Qn行，每行三个正整数i,xi,yi，表示区间[L,R]中i的欧拉函数值是xi,且最大，i的最小质因数或最小正约数是yi；

【样例输入】

5
2
1 2
4 4

【样例输出】

1 1 1
4 2 2

【样例说明】

i 1 2 3 4 5
Ei 1 1 2 2 4
min 1 1 1 2 1

1~2中1和2欧拉值相同都是1，相同时取较小的i，故输出1的相关信息，1没有除自身外的最小质因数，故输出其最小正约数1；

4的欧拉值为2，最小质因数也是2；

【数据范围】

1<=N<=120,0000

1<=Qn<=N/10

1<=Li<=Ri<=N

40%的数据N<=20,0000

100%的数据N<=120,0000

 1     #include<cstdio>
 2     #include<cstring>
 3     #include<iostream>
 4     #include<algorithm>
 5     #include<cmath>
 6     #define maxn 1200005
 7     using namespace std;
 8     void Emine(){
 9         freopen("zhitwo.in","r",stdin);
10         freopen("zhitwo.out","w",stdout);
11     }
12     int read(){
13         int x=0,f=1;char ch=getchar();
14         while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15         while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16         return x*f;
17     }
18     struct node{
19         int id,f;
20         bool operator < (const node & b) const {
21             if(f==b.f) return id<b.id;
22             return f>b.f;
23         }
24     }a[maxn],g[maxn][23];
25     int n,q,f[maxn],pri[maxn],cnt,minn[maxn];
26     bool is_pri[maxn];
27     void getlist(int n){
28         memset(is_pri,true,sizeof(is_pri));
29         int k;a[1].f=1;minn[1]=1;
30         for(int i=2;i<=n;i++){
31             if(is_pri[i]){pri[++cnt]=i;a[i].f=i-1;minn[i]=1;}
32             for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
33                 is_pri[i*pri[j]]=false;
34                 minn[i*pri[j]]=pri[j];
35                 if(i%pri[j]==0){
36                     a[i*pri[j]].f=a[i].f*pri[j];
37                     break;
38                 }
39                 else{
40                     a[i*pri[j]].f=a[i].f*(pri[j]-1);
41                 }
42             }
43         }
44     }
45     node rmq(int l,int r){
46         int k=log(r-l+1)/log(2);
47         return min(g[l][k],g[r-(1<<k)+1][k]);
48     }
49     int main(){
50         Emine();
51         n=read(),q=read();
52         getlist(n);
53         for(int i=1;i<=n;i++)g[i][0].f=a[i].f,g[i][0].id=i;
54         for(int j=1;j<=22;j++)
55             for(int i=1;i+(1<<j)-1<=n;i++)
56                 g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]);
57         while(q--){
58             int l=read(),r=read();
59             node ans=rmq(l,r);
60             printf("%d %d %d\n",ans.id,ans.f,minn[ans.id]);
61         }
62         return 0;
63     }

View Code

1639. 始皇帝的国家道路系统

★☆ 输入文件：qin.in 输出文件：qin.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

战国时期（公元前476年至公元前221年），中国有七个强大的诸侯国---齐、楚、燕、韩、赵、魏和秦。嬴政是秦国的第37代王。通过9年的战争，他终于征服了所有其他六国成为统一中国的始皇帝。嬴政之所以称自己为“秦始皇”，是因为“始皇”在汉语中的意思是“第一个皇帝”。

秦始皇下令建造了许多巨大工程，如长城、兵马俑和庞大的国家公路系统。有一个关于道路系统的故事：

在秦朝有n个城市，始皇帝希望修N-1条路将它们全部连接起来，以便他能从首都咸阳到达每个城市。

虽然始皇帝是一个暴君，但他希望所有道路的总长度都是最小的，这样道路系统可能不会牺牲太多人的性命。一个叫徐福的道士告诉秦始皇，他可以用魔法修路且魔法之路无需耗费资金与人力。但是徐福只能为始皇帝建一条魔法之路。因此，始皇帝不得不决定在哪里修建这条魔法之路。始皇帝希望所有非魔法之路总长度尽可能小，但是徐福想让尽可能多的劳工受益，最终始皇帝决定，A/B的值必须是最大的，其中A是魔法之路连接的两个城市的总人口，B是非魔法之路的总长度。

你能帮始皇帝吗？

一个城市可以看作是一个点，一条道路可以看作是连接两个点的线段。

【输入格式】

第一行一个正整数t(t<=10),表示测试数据组数；

对于每组测试数据：

第一行是城市个数n(2<n<=1000)；

接下来n行，每行3个整数x,y(0<=x,y<=1000),p(p<=100000),其中(x,y)是城市的坐标位置,p是城市的人口数；

【输出格式】

t行，每行一个实数，每个实数表示根据每组测试数据计算出的题中描述的最大比率A/B,结果四舍五入到小数点后2位。

【样例输入】

2
4
1 1 20
1 2 30
200 2 80
200 1 100
3
1 1 20
1 2 30
2 2 40

【样例输出】

65.00
70.00

【提示】

【来源】

hdu 4081

 1     #include<cstdio>
 2     #include<iostream>
 3     #include<cstring>
 4     #include<algorithm>
 5     #include<cmath>
 6     #define maxn 1010
 7     using namespace std;
 8     void Emine(){
 9         freopen("qin.in","r",stdin);
10         freopen("qin.out","w",stdout);
11     }
12     int read(){
13         int x=0,f=1;char ch=getchar();
14         while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15         while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16         return x*f;
17     }
18     struct city{int x,y,w;}e[maxn];
19     int T,n,vis[maxn],pre[maxn];
20     double ans,len,mincost[maxn],path[maxn][maxn],dis[maxn][maxn],d[maxn][maxn];
21     double getdis(city a,city b){return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));}
22     void prim(){
23         memset(d,0,sizeof(d));
24         memset(vis,0,sizeof(vis));
25         memset(path,0,sizeof(path));
26         for(int i=1;i<=n;i++)mincost[i]=dis[1][i],pre[i]=1;
27         vis[1]=1;
28         for(int i=1;i<n;i++){
29             int v=-1;
30             for(int j=1;j<=n;j++)if(!vis[j]&&(mincost[j]<mincost[v]||v==-1))v=j;
31             if(v==-1)break;
32             vis[v]=1;path[v][pre[v]]=path[pre[v]][v]=1,len+=mincost[v];
33             for(int j=1;j<=n;j++){
34                 if(!vis[j]&&dis[v][j]<mincost[j])mincost[j]=dis[v][j],pre[j]=v;
35                 if(vis[j]&&j!=v)d[v][j]=d[j][v]=max(d[j][pre[v]],mincost[v]);  //求环上最大值 
36             }
37         }
38     }
39     void work(){
40         n=read();
41         len=ans=0;
42         for(int i=1;i<=n;i++)e[i].x=read(),e[i].y=read(),e[i].w=read();
43         for(int i=1;i<=n;i++)
44             for(int j=i+1;j<=n;j++)
45                 dis[i][j]=dis[j][i]=getdis(e[i],e[j]);
46         prim();
47         for(int i=1;i<=n;i++){
48             for(int j=i+1;j<=n;j++){
49                 if(path[i][j])ans=max(ans,(double)(e[i].w+e[j].w)/(len-dis[i][j]));  //如果在最小生成树上则直接删除 
50                 else ans=max(ans,double(e[i].w+e[j].w)/(len-d[i][j]));  //否则则删除当前环的最大值
51             }
52         }
53         printf("%.2lf\n",ans);
54     }
55     int main(){
56         Emine();
57         T=read();
58         while(T--)work();
59         return 0;
60     }