Cod sursa(job #2951290)

Utilizator MihaiCostacheCostache Mihai MihaiCostache Data 5 decembrie 2022 21:28:51
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("mins.in");
ofstream fout("mins.out");
int c, d;
long long rez;
int a[1000100], b[1000100];
int main() {
    ///daca segmentul trece prin (i, j), va trece si prin (2*i, 2*j) si prin (3*i, 3*j)
    ///trasam segmente intre (0, 0) si (i, j)
    ///ce putem face sa calculam nr de segmente?
    ///ne intereseaza nr de perechi de nr care sunt prime intre ele
    ///seamana cu problema pairs adica facem ciurul, dar nu mai trebuie sa calculam nrm[i]
    ///avem c/i posibilitati care se divid cu i pt prima coord si d/i posibilitati care se divid cu a doua coord
    ///deci nu mai calculam nrm[i] si sol+=(c/i)*1LL*(d/i);
    fin>>c>>d;
    c--;
    d--;
    int minim=min(c, d);
    rez=1LL*c*d;
    for(int i=2; i<=minim; i++)
    {
        if(a[i]==0) {
            for (int j = 1; 1LL * j * i <= minim; j++) {
                a[1LL * i * j]++;
            }
            for (int j = 1; 1LL * j * i * i <= minim; j++) {
                b[j * i * i] = 1;
            }
        }
        if(b[i]==0)
        {
            long long val=1LL*(c/i)*(d/i);
            if(a[i]%2==1)
            {
                rez-=val;
            }
            else
            {
                rez+=val;
            }
        }
    }
    fout<<rez;
    return 0;
}