lightOj 1370 Bi-shoe and Phi-shoe

本文主要是介绍lightOj 1370 Bi-shoe and Phi-shoe，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
去买bamboo，bamboo的长度是 它的得分小的且与得分互素的数的个数， 如得分为9的bamboo， 小于9并与9互素的有1，2，4，5，7，8共6个，故它的长度为6；每位同学有个幸运数字，需要给每个同学买的bamboo的长度必须大于等于这个幸运数字，bamboo的价格一个单位长度为1xukha，求购买的最小的价格。
分析：
关于欧拉函数的题目。
首先先知道一个素数的欧拉函数的值等于这个数减一。
打个素数表，遍历每个学生的幸运数字，如果这个数字是素数， sum等于这个数+1； 如果不是素数，加一继续遍历。
代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>using namespace std;
typedef long long ll;
const int N = 1000010;
int b[N] = {1, 1, 0}; // 0 和 1都不是素数 void dabiao()
{for(int i = 2 ; i < N ; i++){if(!b[i]){for(int j = i + i ; j <= N ; j += i)b[j] = 1;}}}//素数打表
int main()
{dabiao();int t, n, m, kase = 0;scanf("%d", &t);while(t--){ll sum = 0;scanf("%d", &n);while(n--){scanf("%d", &m);for(int i = m + 1 ; ; i++){if(b[i] == 0)//是素数{sum += i;break;}}}printf("Case %d: %lld Xukha\n", kase++, sum);}return 0;
}

这篇关于lightOj 1370 Bi-shoe and Phi-shoe的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---