0
C++
I have a problem and I wrote the code but when running, CMD it only appears 1 black. Can everyone fix the code for me?
Please display pairs of promised numbers under 100,000 A and B are the pair of promised numbers if the sum of the estimates A (except it) is larger than B 1 unit and the opposite is strange
For exampleThe sum of the divisors of
48 = 76
Total conventions of
75 = 49
And it is proven that A - B always has an even number and some odd numbers. Symbolic male - female.
This is the code:
#include <iostream>
using namespace std;
int sum_divisors(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
if (n % i == 0) {
sum += i;
}
}
return sum;
}
int main() {
for (int A = 1; A < 100000; A++) {
int sumA = sum_divisors(A);
for (int B = A + 2; B < 100000; B++) {
int sumB = sum_divisors(B);
if (sumA == B + 1 && sumB == A + 1) {
cout << A << " - " << B << endl;
}
}
}
return 0;
}
Thêm một bình luận
1 CÂU TRẢ LỜI
0
Your algorithm complexity is O(n^4), so the program runs very slow. Here is my solution in O(nlogn):
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sumDivisors(100001,0);
for(int i=1;i<=50000;i++)
for(int j=i*2;j<=100000;j+=i) sumDivisors[j]+=i;
for(int A=1;A<=100000;A++)
{
int sumDivisorsOfA = sumDivisors[A];
int B = sumDivisorsOfA-1;
if(B<A || B>100000) continue;
int sumDivisorsOfB = sumDivisors[B];
if (sumDivisorsOfB == A+1) {
cout << A << " - " << B << endl;
}
}
return 0;
}
