Cod sursa(job #2951288)

Utilizator MihaiCostacheCostache Mihai MihaiCostache Data 5 decembrie 2022 21:23:46
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 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)
    ///daca avem (i, j) si d=cmmdc(i, j), d!=1 => am traversat (i/d, j/d) si cmmdc(i/d, j/d)=1
    ///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;
    if(c>d)
        swap(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]++;
            }
            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;
}