Cod sursa(job #2949151)

Utilizator rares89_Dumitriu Rares rares89_ Data 29 noiembrie 2022 23:49:35
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>

using namespace std;

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

int c, d, dp[1000005];
long long int cnt;
bool v[1000005];

int main() {
    int c, d;
    fin >> c >> d;
    if(c > d) {
        swap(c, d);
    }
    c--; d--;
    for(int i = 2; i <= c; i++) {
        if(dp[i] == 0) {
            int val = (1LL * i * i <= c ? i * i : c + 1);
            for(int j = i; j <= c; j += i) {
                dp[j]++;
                if(j % val == 0) {
                    v[j] = true;
                }
            }
        }
        if(v[i]) {
            continue;
        }
        if(dp[i] % 2 == 1) {
            cnt += 1LL * (c / i) * (d / i);
        } else {
            cnt -= 1LL * (c / i) * (d / i);
        }
    }
    fout << (1LL * c * d - cnt);;
    return 0;
}