Cod sursa(job #3219735)

Utilizator Toni07Stoica Victor Toni07 Data 1 aprilie 2024 00:29:43
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("mins.in");
ofstream g ("mins.out");

const int nmax = 1e6+1;
int c, d, cnt[nmax], ok[nmax];
long long sol;
int main()
{
    f >> c >> d;
    sol = 1ll * (--c) * (--d);
    for(int i = 2; i <= min(c, d); ++i)
        cnt[i] = 1, ok[i] = INT_MAX;
    for(int i = 2; i * i <= min(c, d); ++i)
        if(cnt[i])
            for(int j = i * i; j <= min(c ,d); j += i)
                cnt[j] = 0;
    for(int i = 2; i <= min(c , d); ++i)
        if(cnt[i])
            for(int j = min(c , d) / i; j >= 1; --j)
                if(ok[j] != INT_MAX)
                    ok[j * i] = 1 + ok[j];
    for(int i = 2; i <= min(c , d); ++i)
        if(ok[i] != INT_MAX)
            if(ok[i] % 2)
                sol -= 1ll * (c / i) * (d / i);
            else
                sol += 1ll * (c / i) * (d / i);
    g << sol << "\n";
    return 0;
}