Cod sursa(job #2532142)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 27 ianuarie 2020 13:50:39
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 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<=1000000;i++)
        mo[i]=-1;
    for(int i=2;i*i<=n;i++)
        for(int j=i*i;j<=n;j+=i*i)
            mo[j]=0;
    for(int i=2;i<=n;i++)
        if(ciur[i]==0)
        for(int j=i;j<=n;j+=i)
            mo[j]=(-1)*mo[j];
}

void rez()
{
    long long rez = 0;

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

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

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