#include <iostream> using namespace std; int sum_of_dil(int n) { int sum = 0; if (n%2==0) { for(int i=1;i<=n/2;++i) if (n%i ==0) sum += i; } else { for(int i=1;i<=n/2;i+=2) if (n%i ==0) sum += i; } return sum; } int main() { int a, b; int count = 0; cin >> a >> b; for(int i=a;i<=b;++i) { for(int j=i+1;j<=b;++j) { if (sum_of_dil(i) == j && sum_of_dil(j) == i) { cout << i << " " << j << endl; count++; } } } if (count ==0) cout << "Absent" << endl; return 0; }

Task from here -> Tyk

Two different positive integers are called friendly if the first one is equal to the sum of the divisors of the second number, except for the second number itself, and the second is equal to the sum of the divisors of the first number, except for the very first number. You need to find all pairs of friendly numbers, both of which belong to the interval from M to N.

Does not pass on time.

  • 2
    Describe the task in your question. - Vlad from Moscow
  • and yes, there are at least 10 ^ 12 operations per cycle. - pavel
  • in short, it is not done at all. - pavel
  • one
    instead of 'int i = 1; i <= n / 2; ++ i' you can read only up to the root with n and at the same time add two dividers at once. (if x is divisible by i, then it is divisible by x / i). And of course do not forget to correctly handle the numbers, which are squares. (i.e., exclude version x / i == i) - KoVadim

2 answers 2

Whistled for 2ms: :)

 #include <iostream> #include <iomanip> using namespace std; struct Frd { int a, b; } f[] = { { 220,284 }, { 1184,1210 }, { 2620,2924 }, { 5020,5564 }, { 6232,6368 }, { 10744,10856 }, { 12285,14595 }, { 17296,18416 }, { 63020,76084 }, { 66928,66992 }, { 67095,71145 }, { 69615,87633 }, { 79750,88730 }, { 100485,124155 }, { 122265,139815 }, { 122368,123152 }, { 141664,153176 }, { 142310,168730 }, { 171856,176336 }, { 176272,180848 }, { 185368,203432 }, { 196724,202444 }, { 280540,365084 }, { 308620,389924 }, { 319550,430402 }, { 356408,399592 }, { 437456,455344 }, { 469028,486178 }, { 503056,514736 }, { 522405,525915 }, { 600392,669688 }, { 609928,686072 }, { 624184,691256 }, { 635624,712216 }, { 643336,652664 }, { 667964,783556 }, { 726104,796696 }, { 802725,863835 }, { 879712,901424 }, { 898216,980984 } }; int main(int argc, const char * argv[]) { int M, N; cin >> M >> N; int count = 0; for(unsigned int i = M>>15; i < sizeof(f)/sizeof(f[0]); ++i) { Frd x = f[i]; if (xa >= M) { if (xb <= N) { ++count; cout << xa << " " << xb << endl; } else break; } } if (count == 0) cout << "Absent\n"; }
  • Is this allowed by the rules? ... But you don’t consider the friendly numbers themselves? .. - Mikhailo
  • @Mikhailo Well, since they write in Wikipedia that "there is still no effective general way of finding all such pairs," and going through a million numbers is really, sorry for the pun, brute force ... Formally, not a single site rule violated. - Harry
  • Well, if so, then ... :) - Mikhailo
  • @Harry why do you not like the standard pair <int, int>? - pavel
  • @pavel write first and second longer than a and b :) - Harry
 int sum=1, i; for (i=3; i*i<n; ++i) if (!(n % i)) sum += i + n/i; if (!(n % i)) sum += i;