You are given two natural numbers A and B. Count how many numbers in the interval [A; B] the sum of divisors will be odd. Restriction (1 <= A <= B <= 1000). I can't do the right amount, I will be glad to any help.

#include<iostream> using namespace std; int main() { int a = 1, b = 6, sum = 0, total = 0; for (int i = a; i <= b; ++i) { for (int j = 1; j< i ; ++j) { if (i % j == 0) sum += j;//Тут проблема if (sum % 2 != 0) ++total; sum = 0; } } cout << "Total:" << total << endl; system("pause"); return 0; }
  • And the number itself must be considered as a divider? You do not consider it as such, and 1 is a divisor. It's right? - Harry
  • what is meant by the sum of dividers, their number or their sum? ... PS Harry made the correct remark - AR Hovsepyan
  • problem in the line sum = 0; - inside the loop, you check not the amount for oddness, but all subtotals. - KoVadim
  • The number itself must be considered. @KoVadim Take out sum = 0; The first cycle did not help, although it should have been. - Nereus
  • I have never said that this is enough. I just hint that this line is definitely out of place - KoVadim

3 answers 3

If we count 1 as a divisor, the number itself is not considered, and work by brute force (although there are more tricky options that benefit from large numbers — for example, factoring into prime numbers, counting the product of odd prime numbers in the decomposition, and based on this even parity of the sum of dividers Maybe there are ways and even more cunning, I do not know ...) - then I would do so, not counting the amount.

 bool odd_d(int n) { bool odd = true; // 1! for(int i = 2; i*i <= n; ++i) { if (n%i) continue; if (i%2) odd = !odd; int d = n/i; if (d == i) continue; if (d%2) odd = !odd; } return odd; } int main(int argc, const char * argv[]) { int a, b, count = 0; cin >> a >> b; for(int n = a; n <= b; ++n) if (odd_d(n)) ++count; cout << count << endl; }
  • The solution method is interesting, but your version is not working, inserting [1; 6] turns out 5, but it should be 3. - Nereus
  • @Nereus Believe ... For 1 - 1, odd; for 2 - 1 - odd, for 3 - 1, odd, for 4 - 1 + 2 - odd, for 5 - 1 - odd, for 6 - 1 + 2 + 3 - even. Total - 5. Where am I wrong? - Harry
  • We consider all dividers, that is, including the number itself. 4 / (1,2,4) - Nereus
  • And you get the more questions that you ask! The first thing I asked you 50 minutes ago was to consider the number itself as a divisor! Excuse me, did you act humanly? answered? Not. I had to give an answer, specifying my version of the TK . You are now with such aplomb - they say, hell is working. Naturally. If you do not give TZ - get HZ. And, by the way, "we think" - yes, you don't think a damn thing, just in your code you DO NOT consider the number itself. - Harry
  • one
    I apologize, there is a newbie, I just did not notice these comments under the post. But it was possible not to react so sharply, the task was clearly set. Thanks for the help. - Nereus

The question is closed, the solution is found. The corrected code will look like this.

 #include<iostream> using namespace std; int main() { int a = 1, b = 6, sum=0, total = 0; for (int i = a; i <= b; ++i) { for (int j = 1; j<= i ; ++j) { if (i % j == 0) sum += j; } if (sum % 2 != 0) ++total; sum = 0; } cout << "Total:" << total << endl; system("pause"); return 0; }
  • And you can count this code for the range a = 10 ^ 8, b = 2 * 10 ^ 9? Or (using long long) up to 10 ^ 18? - MBo
  • @MBo seems to me a little impractical, this code is not designed for such volumes. - Nereus
  • That’s it that is not calculated. This (quadratic) O (n ^ 2) algorithm will be bent by 10 ^ 5. Harry proposed an improvement to O (n ^ 3/2), with which you can work, say, up to 10 million. And with the use of mathematics, a constant time is obtained (at least as long as we can find the root for the constant). If this is a problem with some kind of Olympiad / Contest, then there are restrictions on the data. - MBo
  • @MBo I understand that, and noted that Harry has an interesting solution. Next time I will ask questions more correctly, sorry. - Nereus
  • Well, did the answer offered by me realize for the future? - MBo

The sigma function (σ1 here ) is odd for numbers of the form p^2 and p^2 * 2 (for example, 16, 18, 25)

The number of such numbers in a given range can be calculated as a simple cycle or directly using the root (if this does not lead to rounding errors)

 int odd_sigma(int n) { return (int)sqrt(n) + (int)sqrt(n / 2); } int odds_in_inclusive_range(int a, int b) { return odd_sigma(b) - odd_sigma(a-1); }