企业官网建设流程全解析

P8015 [COCI 2013/2014 #4] GUMA

题目描述

给出一个N + 1 N+1N+1列的矩形，第i ii列必须通过水平切割A i − 1 A_i-1Ai​−1次被等分成A i A_iAi​份，请你求出最少需要几次切割才能按要求分割完。

T i p s : Tips:Tips:一次切割一次可以在一个或多个不一定连续的列上进行分割。

输入格式

第一行，一个正整数N NN，表示这个矩形有N + 1 N+1N+1列；

接下来N + 1 N+1N+1行，每行一个正整数A i A_iAi​，表示第i ii列必须通过水平切割A i − 1 A_i-1Ai​−1次被等分成A i A_iAi​份。

输出格式

一行，一个正整数，表示最小分割数。

输入输出样例 #1

输入 #1

1 2 5

输出 #1

5

输入输出样例 #2

输入 #2

2 3 7 14

输出 #2

15

输入输出样例 #3

输入 #3

9 4 2 4 1 2 2 2 8 4 2

输出 #3

7

说明/提示

【样例解释 #3】

共7 77次切割。

【数据范围】

对于20 % 20\%20%的数据，1 ≤ N ≤ 100 1\le N\le 1001≤N≤100；

对于100 % 100\%100%的数据，1 ≤ N , A i ≤ 10 5 1\le N,A_i\le 10^51≤N,Ai​≤105。

【来源】

本题分值按 COCI 原题设置，满分120 120120。

题目译自 COCI2013-2014 CONTEST #4T4 GUMA。

C++实现

#include<bits/stdc++.h>usingnamespacestd;boolv[1919810];boolvis[314514];intpr[29999],phi[314514],ptr=0;inteuler(intn){//线筛，筛phi函数memset(v,1,sizeof(v));v[0]=v[1]=false;for(inti=2;i<=n;i++){if(v[i]){pr[ptr++]=i;phi[i]=i-1;}for(intj=0;j<=ptr&&(pr[j]*i<n);j++){v[i*pr[j]]=false;phi[i*pr[j]]=phi[i]*phi[pr[j]];if(i%pr[j]==0){phi[i*pr[j]]=phi[i]*pr[j];break;}}}return0;}intmain(intargc,char*argv[]){ios::sync_with_stdio(0);euler(131072);intn,ans=0;cin>>n;n++;while(n--){intA;cin>>A;//每次处理一个数for(inti=1;i*i<=A;i++){if(A%i==0){intj=A/i;//判重+算贡献ans+=(1-vis[i])*phi[i];vis[i]=1;ans+=(1-vis[j])*phi[j];vis[j]=1;cout<<i<<' '<<j<<'\n';}}}cout<<ans;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容