BNU 13288 Bi-shoe and Phi-shoe 【素数筛选】
A -?Bi-shoe and Phi-shoe
Submit?
Status
Description Bamboo Pole-vault is a massively popular sport in Xzhiland. And Master Phi-shoe is a very popular coach for his success. He needs some bamboos for his students,so he asked his assistant Bi-Shoe to go to the market and buy them. Plenty of Bamboos of all possible integer lengths (yes!) are available in the market. According to Xzhila tradition, Score of a bamboo =?Φ (bamboo's length) (Xzhilans are really fond of number theory). For your information,?Φ (n)?= numbers less than?n?which are relatively prime (having no common divisor other than 1) to?n. So,score of a bamboo of length 9 is 6 as 1,2,4,5,7,8 are relatively prime to 9. The assistant Bi-shoe has to buy one bamboo for each student. As a twist,each pole-vault student of Phi-shoe has a lucky number. Bi-shoe wants to buy bamboos such that each of them gets a bamboo with a score greater than or equal to his/her lucky number. Bi-shoe wants to minimize the total amount of money spent for buying the bamboos. One unit of bamboo costs 1 Xukha. Help him. Input Input starts with an integer?T (≤ 100),denoting the number of test cases. Each case starts with a line containing an integer?n (1 ≤ n ≤ 10000)?denoting the number of students of Phi-shoe. The next line contains?n?space separated integers denoting the lucky numbers for the students. Each lucky number will lie in the range?[1,106]. Output For each case,print the case number and the minimum possible money spent for buying the bamboos. See the samples for details. Sample Input 3 5 1 2 3 4 5 6 10 11 12 13 14 15 2 1 1 Sample Output Case 1: 22 Xukha Case 2: 88 Xukha Case 3: 4 Xukha #include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <math.h> #include <ctype.h> #include <time.h> #include <queue> #include <iterator> using namespace std; const int MAXN = 1000100; int n,m,t; int prime[MAXN],ph[MAXN],p[MAXN],q[MAXN]; void solve(int n) { memset(prime,sizeof(prime)); memset(p,sizeof(p)); memset(ph,sizeof(ph)); int t = 0; for (int i = 2; i <= n; i++) { if (p[i] == 0) prime[++t] = i; for (int j = i * 2; j <= n; j+=i) { p[j] = 1; } } t = 1; for (int i = 1; i <= n; i++) { while (i >= prime[t]) { t++; } if (i < prime[t]) ph[i] = prime[t]; } } /* int phi[MAXN]; void Phi(int n) { for (int i = 0; i <= n; i++) phi[i] = 0; phi[1] = 1; for (int i = 2; i <= n; i++) { if (!phi[i]) { for (int j = i; j <= n; j += i) { if (!phi[j]) phi[j] = j; phi[j] = phi[j] / i*(i-1); } } } } */ int main() { int cases = 1; solve(1001000); scanf("%d",&t); while (t--) { long long ans = 0; scanf("%d",&n); for (int i = 0; i < n; i++) scanf("%d",&q[i]); sort(q,q+n); for (int i = 0; i < n; i++) ans += ph[q[i]]; printf("Case %d: %lld Xukhan",cases++,ans); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |