求教EA一道面试题# JobHunting - 待字闺中
s*i
1 楼
https://www.hackerrank.com/challenges/unfriendly-numbers
There is one friendly number and N unfriendly numbers. We want to find how
many numbers are there which exactly divide the friendly number, but does
not divide any of the unfriendly numbers.
Input Format:
The first line of input contains two numbers N and K seperated by spaces. N
is the number of unfriendly numbers, K is the friendly number.
The second line of input contains N space separated unfriendly numbers.
Output Format:
Output the answer in a single line.
Constraints:
1 <= N <= 10^6
1 <= K <= 10^13
1 <= unfriendly numbers <= 10^18
Sample Input:
8 16
2 5 7 4 3 8 3 18
Sample Output:
1
后面几个case很大，常规解法timeout
我的解法是把数组里每个数跟K的最大公约数放进set1，然后再生成K的所有因数set2，
如果set1里的数能整除set2里的一个数，就把它erase。return set1的size。代码如下：
int unfriendlyNumbers(vector < long long int > a,long long int k) {
int ans;
ans = 0;
set < long long int > divisors;
for(long long int i = 1; i<=sqrt(k); i++){
if(k%i == 0){
divisors.insert(i);
divisors.insert(k/i);
}
}
set < long long int > GCDs;
for(long long int j = 0; j
}
set < long long int > ::iterator it1,it2;
for(it1=GCDs.begin();it1!=GCDs.end();it1++){
for(it2=divisors.begin();it2!=divisors.end();it2++){
if((*it1)%(*it2)==0) divisors.erase(*it1);
}
}
ans = divisors.size();
return ans;
}
问题使我提交之后不能通过所有case。求板上大神指点。
There is one friendly number and N unfriendly numbers. We want to find how
many numbers are there which exactly divide the friendly number, but does
not divide any of the unfriendly numbers.
Input Format:
The first line of input contains two numbers N and K seperated by spaces. N
is the number of unfriendly numbers, K is the friendly number.
The second line of input contains N space separated unfriendly numbers.
Output Format:
Output the answer in a single line.
Constraints:
1 <= N <= 10^6
1 <= K <= 10^13
1 <= unfriendly numbers <= 10^18
Sample Input:
8 16
2 5 7 4 3 8 3 18
Sample Output:
1
后面几个case很大，常规解法timeout
我的解法是把数组里每个数跟K的最大公约数放进set1，然后再生成K的所有因数set2，
如果set1里的数能整除set2里的一个数，就把它erase。return set1的size。代码如下：
int unfriendlyNumbers(vector < long long int > a,long long int k) {
int ans;
ans = 0;
set < long long int > divisors;
for(long long int i = 1; i<=sqrt(k); i++){
if(k%i == 0){
divisors.insert(i);
divisors.insert(k/i);
}
}
set < long long int > GCDs;
for(long long int j = 0; j
}
set < long long int > ::iterator it1,it2;
for(it1=GCDs.begin();it1!=GCDs.end();it1++){
for(it2=divisors.begin();it2!=divisors.end();it2++){
if((*it1)%(*it2)==0) divisors.erase(*it1);
}
}
ans = divisors.size();
return ans;
}
问题使我提交之后不能通过所有case。求板上大神指点。
