Cod sursa(job #1688466)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 13 aprilie 2016 15:21:59
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 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 = max(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;
                }
            }
            nr += c / i * 1LL * d / i;
        }
        else{
            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;
}