Cod sursa(job #3237139)

Utilizator tedicTheodor Ciobanu tedic Data 5 iulie 2024 16:35:07
Problema Mins Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 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+=((c-1)/i)*((d-1)/i);
            for(int j=i*2; j<=min(c-1,d-1); j+=i)
                multipli[j]++;
        }
        else
        {
            necoprime-=((c-1)/i)*((d-1)/i);
            for(int j=i*2; j<=min(c-1,d-1); j+=i)
                multipli[j]--;
        }
    }
    cout<<(long long)(c-1)*(d-1)-necoprime;
    return 0;
}