Bi-shoe and Phi-shoe
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,
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
解题思路：
找一个最小的n，使得φ(n) >= x ans 用 long long
AC代码：
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std
;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define Max(x,y) (x)>(y)?(x):(y)
typedef pair
<int,int> PII
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef long double ld
;
const int MOD
= 1e9 + 7;
const ll mod
= 1e9 + 7;
const double eps
= 1e-9;
const ll INF
= 0x3f3f3f3f3f3f3f3fll;
inline int read(){int ret
= 0, sgn
= 1;char ch
= getchar();
while(ch
< '0' || ch
> '9'){if(ch
== '-')sgn
= -1;ch
= getchar();}
while (ch
>= '0' && ch
<= '9'){ret
= ret
*10 + ch
- '0';ch
= getchar();}
return ret
*sgn
;}
inline void Out(int a
){if(a
>9) Out(a
/10);putchar(a
%10+'0');}
ll
qmul(ll a
,ll b
,ll mod
){ll res
=0;while(b
){if(b
&1)res
=(res
+a
)%mod
;a
=(a
+a
)%mod
;b
>>=1;}return res
;}
ll
qpow(ll m
,ll k
,ll mod
){ll res
=1%mod
,t
=m
%mod
;while(k
){if(k
&1)res
=qmul(res
,t
,mod
);t
=qmul(t
,t
,mod
);k
>>=1;}return res
;}
ll
gcd(ll a
,ll b
){if(b
> a
) swap(a
,b
); return b
==0?a
: gcd(b
,a
%b
);}
ll
lcm(ll a
,ll b
){return a
/gcd(a
,b
)*b
;}
ll
inv(ll x
,ll mod
){return qpow(x
,mod
-2,mod
)%mod
;}
int t
= 1,cas
= 1;
int n
,m
;
const int N
= 1e6+7;
bool st
[N
];
int pcnt
,prime
[N
],euler
[N
];
int getEulers(int n
)
{
euler
[1] = 1;
pcnt
= 0;
for (int i
=2; i
<= n
; i
++ ){
if ( !st
[i
] ){
prime
[pcnt
++] = i
;
euler
[i
] = i
-1;
}
for(int j
=0; prime
[j
] <= n
/i
; j
++ ){
st
[ prime
[j
]*i
] = 1;
if (i
%prime
[j
]==0) {
euler
[i
*prime
[j
]]=euler
[i
]*prime
[j
];
break;
}
euler
[i
*prime
[j
]]=euler
[i
]*(prime
[j
]-1);
}
if(euler
[i
] >= 1000000){return i
;}
}
}
signed main()
{
n
= getEulers(N
);
cin
>>t
;
while(t
--){
int n
;
cin
>>n
;
ll ans
= 0;
for(int i
= 0 ; i
< n
; i
++){
int tmp
; cin
>>tmp
;
int tt
= tmp
;
while(euler
[++tt
] < tmp
);
ans
+= tt
;
}
cout
<<"Case "<<cas
++<<": "<<ans
<<" Xukha"<<endl
;
}
}
