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 仔细看了这个网站,印度人开的,还不错。有时间试一试。。 |
|