Cod sursa(job #2975805)

Utilizator francescom_481francesco martinut francescom_481 Data 7 februarie 2023 16:48:06
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<bits/stdc++.h>

using namespace std;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
#endif

ifstream fin("min.in");
ofstream fout("min.out");
#define cin fin
#define cout fout

#define N 100005
#define power 73
#define mod 66666013
#define oo INT_MAX

int prim[N], f[N], n, m, k;
long long rez, nr;


void fa()
{
    for(int i = 2 ; i <= N ; i++)
    {
        if(f[i] == 0)
        {
            prim[++k] = i;
            for(int j = i ; j <= N ; j += i)
            {
                f[j]++;
            }
        }
    }
    for(int i = 1 ; i <= k ; i++)
    {
        for(long long j = 1ll*prim[i]*prim[i] ; j <= N ; j += 1ll*prim[i]*prim[i])
        {
            f[j] = -1;
        }
    }
}

int main()
{
    fa();
    cin >> n >> m;
    for(int i = 1 ; i <= min(m,n) ; i++)
    {
        if(f[i] != -1)
        {
            nr = 1ll*((n-1)/i)*((m-1)/i);
            if(f[i]%2 == 1)
            {
                rez -= nr;
            }
            else rez += nr;
        }
    }
    cout << rez;
    return 0;
}