| Time Limit: 2 second(s) | Memory Limit: 32 MB |
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 |
Output for Sample Input |
|
3 5 1 2 3 4 5 6 10 11 12 13 14 15 2 1 1 |
Case 1: 22 Xukha Case 2: 88 Xukha Case 3: 4 Xukha |
思路：素数打表，欧拉函数，二分。
由于要选最小的，所以假如ola[y]<ola[x]（x<y）那么我们要选的是x，所以如果后面的小于前面的，我们直接把后面的更新为前面的这样欧拉函数值才会是呈递增，那没用二分选取就行了。
#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> #include<stdlib.h> #include<math.h> #include<map> #include<set> using namespace std; bool prime[3300000+5]; int su[300000]; typedef long long LL; typedef struct pp { int x; int id; } ss; ss ola[3300000+5]; int aa[10005]; bool cmp(struct pp nn,struct pp mm) { if(nn.x==mm.x) return nn.id<mm.id; else return nn.x<mm.x; } typedef unsigned long long ll; int main(void) { int i,j,k; for(i=2; i<=7000; i++) { if(!prime[i]) for(j=i; i*j<=(3300000); j++) { prime[i*j]=true; } } int ans=0; for(i=2; i<=(3300000); i++) if(!prime[i]) su[ans++]=i; for(i=1; i<=3300000; i++) { ola[i].id=i; ola[i].x=i; } for(i=0; i<ans; i++) { for(j=1; su[i]*j<=3300000; j++) { ola[su[i]*j].x=ola[su[i]*j].x/(su[i])*(su[i]-1); } } for(i=2; i<3300000; i++) { if(ola[i].x>ola[i+1].x) { ola[i+1].x=ola[i].x; } } scanf("%d",&k); int s; int p,q; for(s=1; s<=k; s++) { LL sum=0; scanf("%d",&p); for(i=0; i<p; i++) { scanf("%d",&aa[i]); int l=2; int r=4*1000000; int zz=0; while(l<=r) { int mid=(l+r)>>1; if(ola[mid].x<aa[i]) { l=mid+1; } else { zz=mid; r=mid-1; } } sum+=ola[zz].id; } printf("Case %d: %lld Xukha ",s,sum); } return 0; }