Cod sursa(job #3359308)

Utilizator Radu_GrigorieGrigorie Radu Stefan Radu_Grigorie Data 26 iunie 2026 19:38:35
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;
ifstream fin("mins.in");
ofstream fout("mins.out");
long long c, d, ciur1[1000005], ciur2[1000005];
void ciurr()
{
    for(int i=2; i<=1000000; i++)
        if(ciur1[i]==0)
            for(int j=i; j<=1000000; j+=i)
                ciur1[j]++;
    for(int i=2; i*i<=1000000; i++)
        if(ciur1[i]==1)
            for(int j=i*i; j<=1000000; j+=i*i)
                ciur2[j]=1;
}
void rez()
{
    fin >> c >> d;
    c--;
    d--;
    long long sol=c*d;
    for(int x=2; x<=min(c, d); x++)
    {
        if(ciur2[x]==0)
        {
            if(ciur1[x]%2==1)
                sol-=(c/x)*(d/x);
            else
                sol+=(c/x)*(d/x);
        }
    }
    fout << sol;
}
int main()
{
    ciurr();
    rez();
    return 0;
}