Rezolvare completă PbInfo #3324 Eratostene0

Cerința

Vi se dau n perechi de numere naturale (i, j), cu i ≤ j. Pentru fiecare pereche trebuie să aflați suma divizorilor tuturor numerelor din șirul i, i + 1, ..., j.

Date de intrare

Fișierul de intrare eratostene0.in conține pe prima linie numărul n, iar pe următoarele n linii câte două numere naturale i1 j1, i2 j2, …, in jn.

Date de ieșire

Fișierul de ieșire eratostene0.out va conține n linii, pe fiecare linie L, L = 1..n, aflându-se un singur număr natural reprezentând suma divizorilor tuturor numerelor corespunzătoare perechii iL jL.

Restricții și precizări

  • 1 ≤ n ≤ 200.000
  • 1 ≤ i ≤ j ≤ 1.000.000

Exemplu

eratostene0.in

4
1 6
3 7
2 5
8 8

eratostene0.out

33
37
20
15

Explicație

1 are suma divizorilor 1.
2 are suma divizorilor 3.
3 are suma divizorilor 4.
4 are suma divizorilor 7.
5 are suma divizorilor 6.
6 are suma divizorilor 12.
7 are suma divizorilor 8.
8 are suma divizorilor 15.

Pentru perechea 1 6 trebuie să aflăm suma divizorilor tuturor numerelor din șirul 1,2,3,4,5,6. Această sumă este 33.
Pentru perechea 3 7 trebuie să aflăm suma divizorilor tuturor numerelor din șirul 3,4,5,6,7. Această sumă este 37.
Pentru perechea 2 5 trebuie să aflăm suma divizorilor tuturor numerelor din șirul 2,3,4,5. Această sumă este 20.
Pentru perechea 8 8 trebuie să aflăm suma divizorilor tuturor numerelor din șirul format doar din 8. Această sumă este 15.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Eratostene0:

#include <bits/stdc++.h>
#define N 1000000
using namespace std;

ifstream  fin("eratostene0.in");
ofstream fout("eratostene0.out");

long long a[1000001];
int n;

int main()
{
    int i, j;
    for (i = 1; i <= N; i++)
        for (j = i; j <= N; j += i)
            a[j] += i;
    for (i = 2; i <= N; i++)
        a[i] += a[i - 1];

    fin >> n;
    while (n--)
    {
        fin >> i >> j;
        fout << (a[j] - a[i - 1]) << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3324 Eratostene0

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3324 Eratostene0 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!