Cod sursa(job #2839102)

Utilizator betybety bety bety Data 25 ianuarie 2022 11:58:30
Problema Mins Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
typedef long long ll;
const ll lim=1e6+4;
bool ok[lim];
ll prod[lim];
ll cnt[lim];
ll c,d,el;
int main()
{
    in>>c>>d; --c,--d;
    if(c>d) swap(c,d);
    for(ll i=1;i<=c;++i)
        prod[i]=1;
    for(ll i=2;i<=c;++i)
    {
        if(!ok[i])
        {
            for(ll j=i;j<=c;j+=i)
                ok[j]=true,
                prod[j]*=i,
                ++cnt[j];
        }
        if(prod[i]==i)
        {
            if(cnt[i]%2==1)
                el+=(c/i)*(d/i);
            else el-=(c/i)*(d/i);
        }
    }
    out<<c*d-el<<'\n';
    return 0;
}