s******i
发帖数: 236 | 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
GCDs.insert(GCD(a[j],k));
}
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。求板上大神指点。 | s**********r
发帖数: 8153 | | l*********8
发帖数: 4642 | 3 倒数第6行：
divisors.erase(*it1) 改成
divisors.erase(*it2)
就行了。
我试过了，可以通过。
N
【在 s******i 的大作中提到】
: 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.
| y***n
发帖数: 1594 | 4 仔细看了这个网站，印度人开的，还不错。有时间试一试。。 |
|
