Cod sursa(job #3237143)

Utilizator tedicTheodor Ciobanu tedic Data 5 iulie 2024 16:38:22
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>

using namespace std;
ifstream cin("mins.in");
ofstream cout("mins.out");
int multipli[1000005];
int main()
{
    int c,d;
    cin>>c>>d;
    ///nr de sol a problemei e nr de perechi (x,y) cu x,y prime(coprime)
    long long int necoprime=0;
    for(int i=2; i<=min(c-1,d-1); i++)
    {
        if(multipli[i]==1)
            continue;
        if(multipli[i]==0)
        {
            necoprime+=1LL*((c-1)/i)*((d-1)/i);
            for(int j=i*2; j<=min(c-1,d-1); j+=i)
                multipli[j]++;
        }
        else
        {
            necoprime-=1LL*((c-1)/i)*((d-1)/i);
            for(int j=i*2; j<=min(c-1,d-1); j+=i)
                multipli[j]--;
        }
    }
    cout<<1LL*(c-1)*(d-1)-necoprime;
    return 0;
}