Cod sursa(job #2020927)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 12 septembrie 2017 10:59:26
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

const int MAXN = (int) 1e6;

bool bad[MAXN + 1];
int prim[MAXN + 1];

int main() {
    FILE *fi, *fout;
    int i, j, c, d;
    fi = fopen("mins.in" ,"r");
    fout = fopen("mins.out" ,"w");
    fscanf(fi,"%d %d " ,&c,&d);
    c--;
    d--;
    if(c > d)
        std::swap(c, d);
    for(i = 2; i <= c; i++)
        if(prim[i] == 0) {
             for(j = i; j <= c; j += i)
                prim[j]++;
             long long val = 1LL * i * i;
             for(long long x = val; x <= c; x += val)
                bad[x] = 1;
        }
    long long ans = 1LL * c * d;
    for(i = 2; i <= c; i++)
       if(bad[i] == 0) {
             if(prim[i] % 2 == 1)
                ans -= 1LL * (c / i) * (d / i);
             else
                ans += 1LL * (c / i) * (d / i);
       }
    fprintf(fout,"%lld" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}