Cod sursa(job #2532134)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 27 ianuarie 2020 13:47:14
Problema Mins Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb

#include <fstream>
#define M 1000005
using namespace std;

ifstream cin("mins.in");
ofstream cout("mins.out");

long long n, m;
char mo[M ];
bool ciur[M ];
int ans[M];

void citire_prelucrare()
{
    cin >> n >> m;
    n--, m--;

    ciur[1]=ciur[0]=1;
    for(int i=2;i*i<=n;i++)
        if(ciur[i]==0)
            for(int j=i*i;j<=n;j+=i)
                ciur[j]=1;

    for(int i = 1 ; i <= M - 5; i++)
        mo[i] = -1;

    for(int i = 2 ; i * i <= M - 5 ; i++)
        for(int j = i * i ; j <= M - 5 ; j += i * i)
            mo[j] = 0;

    for(int i = 2; i <= M - 5; i++)
        if(!ciur[i])
            for(int j = i; j <= M - 5; j += i)
                mo[j] = (-1) * mo[j];
}

void rez()
{
    long long rez = 0;

    for(int i = 2 ; i * i <= M - 5 ; i++)
        rez += (long long) (n / i) * (m / i) * mo[i];

    cout << (long long) n * m - rez;
}

int main()
{
    citire_prelucrare();
    rez();
    return 0;
}