Cod sursa(job #3222666)

Utilizator Allie28Radu Alesia Allie28 Data 11 aprilie 2024 10:59:11
Problema Mins Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;

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

const int LMAX = 1000005;

bool ciur[LMAX];

int main() {
    int c, d, i, j;
    long long s1, s2, sol;
    fin>>c>>d;
    c--;
    d--;
    sol = min(c, d) - 1; //cele de forma (i, i) --> cmmdc este i
    for (i = 2; i <= min(c, d); i++) {
        s1 = s2 = 0; //s1 nr de elem care pot fi si inversate, s2 nr de elemente ce nu pot fi pe primul loc
        if (ciur[i] == 0) { //daca nr este prim
            for (j = i; j <= max(c, d); j = j+i) {
                ciur[j] = 1;
                if (j <= min(c, d)) { //admite inversa
                    s1++;
                }
                else {
                    s2++;
                }
            }
        }
        //s1 numere mai mici decat c si d, s2 numere intre c si d
        sol = sol + s1*s2 + s1*(s1 - 1);
    }
    fout<<c*d - sol;


    fin.close();
    fout.close();
    return 0;
}