本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!