Cod sursa(job #1688482)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 13 aprilie 2016 15:32:57
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
#define DIM 1000005
using namespace std;
int c, d, n, i, j;
long long nr, x;
char f[DIM], ok[DIM];
int nrd[DIM];
ifstream fin("mins.in");
ofstream fout("mins.out");
int main(){
    fin>> c >> d;
    c--;
    d--;
    n = min(c, d);
    for(i = 2; i <= n; i++){
        if(f[i] == 0){
            for(j = i + i; j <= n; j += i){
                f[j] = 1;
                nrd[j]++;
                if(j % (i * i) == 0){
                    ok[j] = 1;
                }
            }
            nrd[i] = 1;
        }
        if(ok[i] == 0){
            x = (c / i) * 1LL * (d / i);
            if(nrd[i] % 2 == 1){
                nr += x;
            }
            else{
                nr -= x;
            }
        }
    }
    nr = c * 1LL * d - nr;
    fout<< nr <<"\n";
    return 0;
}