Cod sursa(job #2027593)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 26 septembrie 2017 13:28:49
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>

int prim[1000001];
bool estiUratSiProst[1000001];
int main(){
    FILE*fi,*fo;
    fi = fopen("mins.in","r");
    fo = fopen("mins.out","w");

    int c, d;
    fscanf(fi,"%d%d", &c, &d);
    c--;
    d--;
    if(c > d){
        int aux = c;
        c = d;
        d = aux;
    }

    for(int i = 2; i <= c; i++){
        if(prim[i] == 0){
            for(int j = i; j <= c; j += i)
                prim[j]++;
            for(long long j = 1LL * i * i; j <= c; j += 1LL * i * i)
                estiUratSiProst[j] = 1;
        }
    }

    long long rez = 1LL * c * d;
    for(int i = 2; i <= c; i++){
        if(!estiUratSiProst[i]){
            if(prim[i] % 2 == 1)
                rez = rez - 1LL * (c / i) * (d / i);
            else
                rez = rez + 1LL * (c / i) * (d / i);
        }
    }

    fprintf(fo,"%lld", rez);
    fclose(fi);
    fclose(fo);
    return 0;
}