Cod sursa(job #2875461)

Utilizator lolismekAlex Jerpelea lolismek Data 21 martie 2022 17:50:20
Problema Mins Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <bitset>

#define int long long

using namespace std;

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

const int N = 1e6;
int ciur[N + 1];
bitset <N + 1> mpp; // nu vrem niciun factor la o putere mai mare de doi

signed main(){
    int c, d;
    fin >> c >> d;
    c--, d--;
    if(c > d) swap(c, d);
    int ans = c * d;
    for(int i = 2; i <= c; i++){
        if(!ciur[i]){
            for(int j = i; j <= c; j += i) ciur[j]++;
            for(int j = i * i; j <= c; j += i * i) mpp[j] = 1;
        }
        if(!mpp[i]){
            // PINEX:
            if(ciur[i] % 2 == 0) ans += (c / i) * (d / i);
            else ans -= (c / i) * (d / i);
        }
    }
    fout << ans;
    return 0;
}