P8015 [COCI 2013/2014 #4] GUMA题目描述给出一个N 1 N1N1列的矩形第i ii列必须通过水平切割A i − 1 A_i-1Ai​−1次被等分成A i A_iAi​份请你求出最少需要几次切割才能按要求分割完。T i p s : Tips:Tips:一次切割一次可以在一个或多个不一定连续的列上进行分割。输入格式第一行一个正整数N NN表示这个矩形有N 1 N1N1列接下来N 1 N1N1行每行一个正整数A i A_iAi​表示第i ii列必须通过水平切割A i − 1 A_i-1Ai​−1次被等分成A i A_iAi​份。输出格式一行一个正整数表示最小分割数。输入输出样例 #1输入 #11 2 5输出 #15输入输出样例 #2输入 #22 3 7 14输出 #215输入输出样例 #3输入 #39 4 2 4 1 2 2 2 8 4 2输出 #37说明/提示【样例解释 #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实现#includebits/stdc.husingnamespacestd;boolv[1919810];boolvis[314514];intpr[29999],phi[314514],ptr0;inteuler(intn){//线筛筛phi函数memset(v,1,sizeof(v));v[0]v[1]false;for(inti2;in;i){if(v[i]){pr[ptr]i;phi[i]i-1;}for(intj0;jptr(pr[j]*in);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,ans0;cinn;n;while(n--){intA;cinA;//每次处理一个数for(inti1;i*iA;i){if(A%i0){intjA/i;//判重算贡献ans(1-vis[i])*phi[i];vis[i]1;ans(1-vis[j])*phi[j];vis[j]1;couti j\n;}}}coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容