Cod sursa(job #3359307)

Utilizator Radu_GrigorieGrigorie Radu Stefan Radu_Grigorie Data 26 iunie 2026 19:29:43
Problema Mins Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
using namespace std;
ifstream fin("mins.in");
ofstream fout("mins.out");
long long c, d, ciur[1005], prime[170], nrprime, lib, nrdivprim, sol, cx;
void ciurr()
{
    for(int i=2; i*i<=1000; i++)
        if(ciur[i]==0)
            for(int j=i*i; j<=1000; j+=i)
                ciur[j]=1;
    for(int i=2; i<=1000; i++)
        if(ciur[i]==0)
            prime[++nrprime]=i;
}
void rez()
{
    fin >> c >> d;
    c--;
    d--;
    sol=c*d;
    for(int x=2; x<=min(c, d); x++)
    {
        lib=1;
        nrdivprim=0;
        cx=x;
        for(int i=1; i<=nrprime; i++)
        {
            if(x%prime[i]==0)
            {
                nrdivprim++;
                cx/=prime[i];
            }
            if(x%(prime[i]*prime[i])==0)
            {
                lib=0;
                break;
            }
        }
        if(lib==1)
        {
            if(cx>1)
                nrdivprim++;
            if(nrdivprim%2==1)
                sol-=(c/x)*(d/x);
            else
                sol+=(c/x)*(d/x);
        }
    }
    fout << sol;
}
int main()
{
    ciurr();
    rez();
    return 0;
}